Computing minimum geodetic sets of proper interval graphs
Tınaz Ekim, Aysel Erey, Pinar Heggernes, Pim van 't Hof and Daniel Meister
This paper appeared in the proceedings of
LATIN 2012, the 10th Latin American Theoretical Informatics Symposium (held on April 16-20, 2012 in Arequipa, Peru), Lecture Notes in Computer Science, vol. 7256, pp. 279-290, 2012.
[DOI]
Abstract:
We show that the geodetic number of proper interval graphs can be computed in polynomial time. This problem is NP-hard on chordal graphs and on bipartite weakly chordal graphs. Only an upper bound on the geodetic number of proper interval graphs has been known prior to our result.