On the computational complexity of the strong geodetic recognition problem

DOI10.1051/RO/2024120MaRDI QIDQ6658857zbMATH OpenFDO

Authors Carlos Vinícius G. C. Lima, Vinícius F. dos Santos, Joãao H. G. Sousa, Sebastián Urrutia

Publication date 8 January 2025

Published in RAIRO. Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1051/RO/2024120

zbMATH Keywords

coveringNP-completenessstrong geodetic numberstrong geodetic recognition

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Strong geodetic problem on complete multipartite graphs
• Computational Complexity of Geodetic Set
• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• Strong geodetic problem in networks
• Hardness and approximation for the geodetic set problem in some graph classes

Cites work

• A characterization of block graphs
• A construction of geodetic graphs based on pulling subgraphs homeomorphic to complete graphs
• Block decomposition approach to compute a minimum geodetic set
• Computational Complexity of Geodetic Set
• Computing minimum geodetic sets of proper interval graphs
• Dominating sets for split and bipartite graphs
• Fundamentals of parameterized complexity
• Geodetic graphs of diameter two
• Kernel bounds for disjoint cycles and disjoint paths
• New proof of a characterization of geodetic graphs
• On the approximation hardness of geodetic set and its variants
• On The Edge Geodetic Number Of A Graph
• On the geodetic number and related metric sets in Cartesian product graphs
• On the hardness of finding the geodetic number of a subcubic graph
• On the Steiner, geodetic and hull numbers of graphs
• Parameterized algorithms
• Reducibility among combinatorial problems
• Some remarks on the geodetic number of a graph
• Strong geodetic cores and Cartesian product graphs
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes
• Strong geodetic problem in grid-like architectures
• Strong geodetic problem in networks
• Strong geodetic problem on Cartesian products of graphs
• Strong geodetic problem on complete multipartite graphs
• The complexity of satisfiability problems
• The geodetic number of a graph
• The hull and geodetic numbers of orientations of graphs
• The upper connected geodetic number and forcing connected geodetic number of a graph
• What Is Known About Vertex Cover Kernelization?

Cited in

(4)

• The geodesic cover problem for butterfly networks
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number
• Algorithms and complexity for geodetic sets on interval and chordal graphs
• Metric dimension and geodetic set parameterized by vertex cover

This page was built for publication: On the computational complexity of the strong geodetic recognition problem

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