Computing minimum geodetic sets of proper interval graphs

DOI10.1007/978-3-642-29344-3_24zbMATH Open1353.68119OpenAlexW2204988559MaRDI QIDQ2894472FDOQ2894472

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

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

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)

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
• Hull and geodetic numbers for some classes of oriented graphs
• Strong geodetic problem in grid-like architectures
• Strong geodetic number of complete bipartite graphs and of graphs with specified diameter
• 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
• Title not available (Why is that?)
• On the computational complexity of the strong geodetic recognition problem
• Strong geodetic number of graphs and connectivity
• Block decomposition approach to compute a minimum geodetic set
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• 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)