Computing Minimum Geodetic Sets of Proper Interval Graphs

DOI10.1007/978-3-642-29344-3_24zbMath1353.68119OpenAlexW2204988559MaRDI QIDQ2894472

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

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)

Related Items (16)

Complexity aspects of the triangle path convexity ⋮ On the geodetic hull number of \(P_{k}\)-free graphs ⋮ Strong geodetic number of complete bipartite graphs and of graphs with specified diameter ⋮ Well-partitioned chordal graphs ⋮ Geodetic Convexity Parameters for Graphs with Few Short Induced Paths ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ Three problems on well-partitioned chordal graphs ⋮ Unnamed Item ⋮ Strong geodetic number of graphs and connectivity ⋮ Strong geodetic problem in grid-like architectures ⋮ Geodetic convexity parameters for \((q, q - 4)\)-graphs ⋮ Strong geodetic problem in networks ⋮ 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 ⋮ Strong geodetic problem on complete multipartite graphs

This page was built for publication: Computing Minimum Geodetic Sets of Proper Interval Graphs