Computing minimum geodetic sets of proper interval graphs

DOI10.1007/978-3-642-29344-3_24MaRDI QIDQ2894472zbMATH OpenOpenAlexFDO

Authors Tınaz Ekim, Aysel Erey, Pinar Heggernes, Pim Van 't Hof, Daniel Meister

Publication date 29 June 2012

Published in LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29344-3_24

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• Some remarks on the geodetic number of a graph
• scientific article; zbMATH DE number 5531985
• Hardness and approximation for the geodetic set problem in some graph classes
• scientific article; zbMATH DE number 969092

Cited in

(26)

• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• Strong geodetic number of graphs and connectivity
• Geodetic convexity parameters for \((q, q - 4)\)-graphs
• Well-partitioned chordal graphs
• Strong geodetic problem in networks
• On the geodetic hull number of \(P_{k}\)-free graphs
• Three problems on well-partitioned chordal graphs
• Complexity aspects of the triangle path convexity
• Block decomposition approach to compute a minimum geodetic set
• Geodetic convexity parameters for graphs with few short induced paths
• Strong geodetic problem on complete multipartite graphs
• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Hull and geodetic numbers for some classes of oriented graphs
• Algorithms and complexity for geodetic sets on partial grids
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)
• Maximum cut on interval graphs of interval count four is NP-complete
• Semi-proper interval graphs
• On the computational complexity of the strong geodetic recognition problem
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• The closed geodetic game: algorithms and strategies
• Enumerating minimal solution sets for metric graph problems
• Enumerating minimal solution sets for metric graph problems
• Strong geodetic problem in grid-like architectures
• Algorithms and complexity for geodetic sets on interval and chordal graphs
• Algorithms and hardness for geodetic set on tree-like digraphs

This page was built for publication: Computing minimum geodetic sets of proper interval graphs

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