Block decomposition approach to compute a minimum geodetic set
RAIRO - Operations Research - Recherche Opérationnelle, Volume 48 (2014) no. 4, pp. 497-507.

In this paper, we develop a divide-and-conquer approach, called block decomposition, to solve the minimum geodetic set problem. This provides us with a unified approach for all graphs admitting blocks for which the problem of finding a minimum geodetic set containing a given set of vertices (g-extension problem) can be efficiently solved. Our method allows us to derive linear time algorithms for the minimum geodetic set problem in (a proper superclass of) block-cacti and monopolar chordal graphs. Also, we show that hull sets and geodetic sets of block-cacti are the same, and the minimum geodetic set problem is NP-hard in cobipartite graphs. We conclude by pointing out several interesting research directions.

DOI: 10.1051/ro/2014019
Classification: 05C12, 05C85
Keywords: convexity, geodetic set, hull set, graph classes
@article{RO_2014__48_4_497_0,
     author = {Ekim, T{\i}naz and Erey, Aysel},
     title = {Block decomposition approach to compute a minimum geodetic set},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {497--507},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     year = {2014},
     doi = {10.1051/ro/2014019},
     mrnumber = {3264390},
     zbl = {1301.05100},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2014019/}
}
TY  - JOUR
AU  - Ekim, Tınaz
AU  - Erey, Aysel
TI  - Block decomposition approach to compute a minimum geodetic set
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2014
SP  - 497
EP  - 507
VL  - 48
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2014019/
DO  - 10.1051/ro/2014019
LA  - en
ID  - RO_2014__48_4_497_0
ER  - 
%0 Journal Article
%A Ekim, Tınaz
%A Erey, Aysel
%T Block decomposition approach to compute a minimum geodetic set
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2014
%P 497-507
%V 48
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2014019/
%R 10.1051/ro/2014019
%G en
%F RO_2014__48_4_497_0
Ekim, Tınaz; Erey, Aysel. Block decomposition approach to compute a minimum geodetic set. RAIRO - Operations Research - Recherche Opérationnelle, Volume 48 (2014) no. 4, pp. 497-507. doi : 10.1051/ro/2014019. http://archive.numdam.org/articles/10.1051/ro/2014019/

[1] A.A. Bertossi, Dominating sets for split and bipartite graphs. Inf. Proc. Lett. 19 (1984) 37-40. | MR | Zbl

[2] B. Brešar and A. Tepeh Horvat, On the geodetic number of median graphs. Discrete Math. 308 (2008) 4044-4051. | MR | Zbl

[3] B. Brešar, S. Klavžar and A. Tepeh Horvat, On the geodetic number and related metric sets in Cartesian product graphs. Discrete Math. 308 (2008) 5555-5561. | MR | Zbl

[4] F. Buckley and F. Harary, Geodetic games for graphs. Questiones Math. 8 (1986) 321-334. | MR | Zbl

[5] J. Cáceres, C. Hernando, M. Mora, I.M. Pelayo and M.L. Puertas, On the geodetic and the hull numbers in strong product graphs. Comput. Math. Appl. 60 (2010) 3020-3031. | MR | Zbl

[6] J. Cáceres, A. Marquez, O. R. Oellerman, M. L. Puertas, Rebuilding convex sets in graphs. Discrete Math. 297 (2005) 26-37. | MR | Zbl

[7] S.R. Canoy, G.B. Cagaanan and S.V. Gervacio, Convexity, Geodetic and Hull Numbers of the Join of Graphs. Utilitas Mathematica 71 (2006) 143-159. | MR | Zbl

[8] G.-B. Chae, E.M. Palmer and W.C. Siu, Geodetic number of random graphs of diameter 2. Aust. J. Combinatorics 26 (2002) 11-20. | MR | Zbl

[9] M.C. Dourado, J.G. Gimbel, J. Kratochvíl, F. Protti and J.L. Szwarcfiter, On the computation of the hull number of a graph. Discrete Math. 309 (2009) 5668-5674. | MR | Zbl

[10] M.C. Dourado, F. Protti, D. Rautenbach and J.L. Szwarcfiter, Some remarks on the geodetic number of a graph. Discrete Math. 310 (2010) 832-837. | MR | Zbl

[11] T. Ekim, A. Erey, P. Heggernes, P. van't Hof and D. Meister, Computing Minimum Geodetic Sets of Proper Interval Graphs. Proceedings of LATIN 2012. Lect. Notes Comput. Sci. 7256 (2012) 279-290.

[12] T. Ekim, P. Hell, J. Stacho and D. De Werra, Polar chordal graphs. Discrete Appl. Math. 156 (2008) 2469-2479. | MR | Zbl

[13] A. Erey, Convexity in graphs. Master's Thesis, Boğaziçi University (2011).

[14] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Meth. 7 (1986) 433-442. | MR | Zbl

[15] O. Gerstel and S. Zaks, A new characterization of tree medians with applications to distributed sorting. Networks 24 (1994) 23-29. | MR | Zbl

[16] A. Hansberg and L. Volkmann, On the geodetic and geodetic domination numbers of a graph. Discrete Math. 310 (2010) 2140-2146. | MR | Zbl

[17] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph. Math. Comput. Modell. 17 (1993) 89-95. | MR | Zbl

[18] T.W. Haynes, M.A. Henning and C. Tiller, Geodetic achievement and avoidance games for graphs. Quaestiones Math. 26 (2003) 389-397. | MR | Zbl

[19] C. Hernando, T. Jiang, M. Mora, I.M. Pelayo and C. Seara, On the Steiner, geodetic and hull numbers of graphs Discrete Math. 293 (2005) 139-154. | MR | Zbl

[20] E. Howorka, A characterization of ptolemaic graphs. J. Graph Theory 5 (1981) 323-331. | MR | Zbl

[21] A.N.C. Kang and D.A. Ault, Some properties of a centroid of a free tree. Inf. Process. Lett. 4 (1975) 18-20. | MR | Zbl

[22] M.M. Kanté and L. Nourine, Polynomial Time Algorithms for Computing a Minimum Hull Set in Distance-Hereditary and Chordal Graphs. Proceedings of SOFSEM 2013. Lect. Notes Comput. Sci. 7741 (2013) 268-279. | MR

[23] S.L. Mitchell, Another characterization of the centroid of a tree. Discrete Math. 24 (1978) 277-280. | MR | Zbl

[24] H.M. Mulder, The Interval Function of a Graph. Mathematish Centrum, Tract. 132, Amsterdam (1981). | MR | Zbl

[25] M. Necásková, A note on the achievement geodetic games. Questiones Math. 12 (1988) 115-119. | MR | Zbl

[26] C. Pandu Rangan, K.R. Parthasarathy and V. Prakash, On the g-centroidal problem in special classes of perfect graphs. Ars Combinatoria 50 (1998) 267-278. | MR | Zbl

[27] F.S. Roberts, Indifference graphs, in Proof techniques in graph theory, edited by F. Harary, Academic Press (1969) 139-146. | MR | Zbl

[28] P. Veeraraghavan, An efficient g-centroid location algorithm for cographs. Inter. J. Math. Math. Sci. 9 (2005) 1405-1413. | MR | Zbl

[29] P. Veeraraghavan, Application of g-convexity in mobile ad hoc networks, in 6th International Conference on Information Technology in Asia 2009, Kuching, Sarawak, Malaysia, vol. CITA 09 (2009) 33-38.

[30] M.J.L. Van De Vel, Theory of convex structures. North-Holland (1993). | MR | Zbl

[31] F.H. Wang, Y.L. Wang and J.M. Chang, The lower and upper forcing geodetic numbers of block-cactus graphs. Eur. J. Oper. Res. 175 (2006) 238-245. | MR | Zbl

Cited by Sources: