On the parameterized complexity of the geodesic hull number

DOI10.1016/J.TCS.2019.05.005MaRDI QIDQ2272396zbMATH OpenOpenAlexWikidataFDO

Authors Mamadou Moustapha Kanté, Thiago Marcilon, Rudini M. Sampaio

Publication date 10 September 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.05.005

zbMATH Keywords

geodesic convexityhull numberparameterized complexitytreewidth

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the geodetic hull number of \(P_{k}\)-free graphs
• The geodetic hull number is hard for chordal graphs
• On the hull number of some graph classes
• Parameterized complexity of geodetic set
• Geodetic convexity parameters for graphs with few short induced paths

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity results related to monophonic convexity
• Convex sets in graphs. II: Minimal path convexity
• Convexity in Graphs and Hypergraphs
• Convexity in partial cubes: the hull number
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• Inapproximability results for graph convexity parameters
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• On local convexity in graphs
• On slowly percolating sets of minimal size in bootstrap percolation
• On the Carathéodory number for the convexity of paths of order three
• On the complexity of k-SAT
• On the computation of the hull number of a graph
• On the geodetic hull number of \(P_{k}\)-free graphs
• On the hull number of triangle-free graphs
• The hull number of a graph
• Which problems have strongly exponential complexity?

Cited in

(8)

• The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces
• The hull number in the convexity of induced paths of order \(3\)
• \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers
• The geodetic hull number is hard for chordal graphs
• Parameterized complexity of geodetic set
• Parameterized Complexity of Geodetic Set
• On the hull and interval numbers of oriented graphs
• Geodetic set on graphs of constant pathwidth and feedback vertex set number

This page was built for publication: On the parameterized complexity of the geodesic hull number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272396)