Computing minimum geodetic sets of proper interval graphs. (English) Zbl 1353.68119
Fernández-Baca, David (ed.), LATIN 2012: Theoretical informatics. 10th Latin American symposium, Arequipa, Peru, April 16–20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29343-6/pbk). Lecture Notes in Computer Science 7256, 279-290 (2012).
Summary: 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.
For the entire collection see [Zbl 1239.68008].
For the entire collection see [Zbl 1239.68008].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
