Computing minimum geodetic sets of proper interval graphs
10th Latin American Symposiumon Theoretical Informatics, LATIN 2012, Arequipa, Peru, 16 - 20 Nisan 2012, cilt.7256 LNCS, ss.279-290, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 7256 LNCS
- Doi Numarası: 10.1007/978-3-642-29344-3_24
- Basıldığı Şehir: Arequipa
- Basıldığı Ülke: Peru
- Sayfa Sayıları: ss.279-290
- Boğaziçi Üniversitesi Adresli: Evet
Özet
We show that the geodetic number of proper interval graphs can be computed in polynomial time. This problem is -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. © 2012 Springer-Verlag Berlin Heidelberg.