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

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

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

(20)

• Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
• Complexity aspects of the triangle path convexity
• Strong geodetic problem in grid-like architectures
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• Hull and geodetic numbers for some classes of oriented graphs
• Well-partitioned chordal graphs
• Geodetic convexity parameters for \((q, q - 4)\)-graphs
• Algorithms and complexity for geodetic sets on partial grids
• Strong geodetic problem in networks
• Three problems on well-partitioned chordal graphs
• On the geodetic hull number of \(P_{k}\)-free graphs
• Strong geodetic problem on complete multipartite graphs
• Geodetic convexity parameters for graphs with few short induced paths
• Semi-proper interval graphs
• Strong geodetic number of graphs and connectivity
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)
• On the computational complexity of the strong geodetic recognition problem
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• Block decomposition approach to compute a minimum geodetic set
• Maximum cut on interval graphs of interval count four is NP-complete

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)