Abstract
We show that the geodetic number of proper interval graphs can be computed in polynomial time. This problem is \(\mbox{\rm 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.
This work is supported by the Research Council of Norway.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bertossi, A.A.: Dominating sets for split and bipartite graphs. Information Processing Letters 19, 37–40 (1984)
Brandstädt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999)
Buckley, F., Harary, F.: Geodetic games for graphs. Questiones Mathematicae 8, 321–334 (1986)
Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time recognition of unit interval graphs. Information Processing Letters 55, 99–104 (1995)
Dewdney, A.K.: Fast Turing reductions between problems in NP. Technical Report 71, Department of Computer Science, University of Western Ontario (1981)
Dourado, M.C., Gimbel, J.G., Kratochvíl, J., Protti, F., Szwarcfiter, J.L.: On the computation of the hull number of a graph. Discrete Mathematics 309, 5668–5674 (2009)
Dourado, M.C., Protti, F., Rautenbach, D., Szwarcfiter, J.L.: Some remarks on the geodetic number of a graph. Discrete Mathematics 310, 832–837 (2010)
Farber, M., Jamison, R.E.: Convexity in graphs and hypergraphs. SIAM Journal on Algebraic and Discrete Methods 7, 433–442 (1986)
Gerstel, O., Zaks, S.: A new characterization of tree medians with applications to distributed sorting. Networks 24, 23–29 (1994)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. Elsevier (2004)
Harary, F., Loukakis, E., Tsouros, C.: The geodetic number of a graph. Mathematical Computation Modelling 17, 89–95 (1993)
Haynes, T.W., Henning, M.A., Tiller, C.: Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae 26, 389–397 (2003)
Hernandoa, C., Jiang, T., Mora, M., Pelayo, I.M., Seara, C.: On the Steiner, geodetic and hull numbers of graphs. Discrete Mathematics 293, 139–154 (2005)
Kang, A.N.C., Ault, D.A.: Some properties of a centroid of a free tree. Information Processing Letters 4, 18–20 (1975)
Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Computers & Mathematics with Applications 25, 15–25 (1993)
Mitchell, S.L.: Another characterization of the centroid of a tree. Discrete Mathematics 24, 277–280 (1978)
Necásková, M.: A note on the achievement geodetic games. Quaestiones Mathematicae 12, 115–119 (1988)
Pandu Rangan, C., Parthasarathy, K.R., Prakash, V.: On the g-centroidal problem in special classes of perfect graphs. Ars Combinatoria 50, 267–278 (1998)
Prakash, V.: An Efficient g-centroid Location Algorithm for Cographs. International Journal of Mathematics and Mathematical Sciences 9, 1405–1413 (2005)
Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139–146. Academic Press (1969)
Spinrad, J., Brandstädt, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Mathematics 18, 279–292 (1987)
Veeraraghavan, P.: Application of g-convexity in mobile ad hoc networks. In: Proceedings of CITA 2009, pp. 33–38 (2009)
Wang, F.H., Wang, Y.L., Chang, J.M.: The lower and upper forcing geodetic numbers of block-cactus graphs. European Journal of Operational Research 175, 238–245 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ekim, T., Erey, A., Heggernes, P., van ’t Hof, P., Meister, D. (2012). Computing Minimum Geodetic Sets of Proper Interval Graphs. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-29344-3_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29343-6
Online ISBN: 978-3-642-29344-3
eBook Packages: Computer ScienceComputer Science (R0)