Computational Complexity of Geodetic Set

DOI10.1080/00207160210954MaRDI QIDQ4543521zbMATH OpenOpenAlexFDO

Authors Mustafa Atici

Publication date 2 December 2002

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160210954

zbMATH Keywords

complexitydecision problemgeodetic numbergeodetic setNP-complete

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the hardness of finding the geodetic number of a subcubic graph
• Parameterized complexity of geodetic set
• Some remarks on the geodetic number of a graph
• Hardness and approximation for the geodetic set problem in some graph classes
• scientific article; zbMATH DE number 5531985

Cited in

(35)

• The forcing total restrained geodetic number and the total restrained geodetic number of a graph: realizability and complexity
• Total restrained geodetic number of graphs
• On the hardness of finding the geodetic number of a subcubic graph
• On the geodetic number of complementary prisms
• The 2-edge geodetic number and graph operations
• Algorithmic upper bounds for graph geodetic number
• An \(O( mn^2)\) algorithm for computing the strong geodetic number in outerplanar graphs
• On the computational complexities of various geography variants
• Well-partitioned chordal graphs
• On the toll number of a graph
• The geodetic number of the lexicographic product of graphs
• Strong geodetic problem in networks
• Geodetic number of powers of cycles
• On pitfalls in computing the geodetic number of a graph
• Three problems on well-partitioned chordal graphs
• On the convexity of paths of length two in undirected graphs
• Block decomposition approach to compute a minimum geodetic set
• scientific article; zbMATH DE number 1156614 (Why is no real title available?)
• On The Edge Geodetic Number Of A Graph
• Graphs with large total geodetic number
• Parameterized complexity of geodetic set
• Strong geodetic problem on complete multipartite graphs
• Discrete Sturm-Liouville problems with nonlinear parameter in the boundary conditions
• Algorithms and complexity for geodetic sets on partial grids
• Parameterized Complexity of Geodetic Set
• On the computational complexity of the strong geodetic recognition problem
• The closed geodetic game: algorithms and strategies
• On the strong geodeticity in the corona type product of graphs
• Geodetic numbers of tensor product and lexicographic product of graphs
• Monophonic number of Kneser graphs and strongly 2-monophonic graphs
• Hardness and approximation for the geodetic set problem in some graph classes
• Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs
• Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs
• Some remarks on the geodetic number of a graph
• Complexity results related to monophonic convexity

This page was built for publication: Computational Complexity of Geodetic Set

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