Computational Complexity of Geodetic Set
From MaRDI portal
Publication:4543521
DOI10.1080/00207160210954zbMath0999.05027MaRDI QIDQ4543521
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
68Q25: Analysis of algorithms and problem complexity
05C12: Distance in graphs
05C85: Graph algorithms (graph-theoretic aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
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, Parameterized Complexity of Geodetic Set, 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, 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, Well-partitioned chordal graphs, A general framework for path convexities, 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