On the hardness of finding the geodetic number of a subcubic graph
From MaRDI portal
Publication:1708262
DOI10.1016/j.ipl.2018.02.012zbMath1476.05041OpenAlexW2791124391MaRDI QIDQ1708262
Lucia Draque Penso, Victor R. Ramos, Letícia R. Bueno, Fábio Protti, Uéverton S. Souza, Dieter Rautenbach
Publication date: 5 April 2018
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2018.02.012
Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (13)
Parameterized Complexity of Geodetic Set ⋮ Well-partitioned chordal graphs ⋮ A general framework for path convexities ⋮ Formulas in connection with parameters related to convexity of paths on three vertices: caterpillars and unit interval graphs ⋮ \(P_3\)-convexity on graphs with diameter two: computing hull and interval numbers ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Target set selection with maximum activation time ⋮ Three problems on well-partitioned chordal graphs ⋮ Unnamed Item ⋮ Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes ⋮ Strong geodetic cores and Cartesian product graphs ⋮ Strong geodetic problem on complete multipartite graphs ⋮ Parameterized Complexity of Geodetic Set
Cites Work
- Hull number: \(P_5\)-free graphs and reduction rules
- Some remarks on the geodetic number of a graph
- On the geodetic and geodetic domination numbers of a graph
- On the geodetic number and related metric sets in Cartesian product graphs
- The hull and geodetic numbers of orientations of graphs
- The upper connected geodetic number and forcing connected geodetic number of a graph
- Some APX-completeness results for cubic graphs
- The geodetic hull number is hard for chordal graphs
- On the geodetic hull number of \(P_{k}\)-free graphs
- On The Edge Geodetic Number Of A Graph
- Computational Complexity of Geodetic Set
This page was built for publication: On the hardness of finding the geodetic number of a subcubic graph
