# Block decomposition approach to compute a minimum geodetic set

RAIRO - Operations Research - Recherche Opérationnelle (2014)

- Volume: 48, Issue: 4, page 497-507
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topEkim, Tınaz, and Erey, Aysel. "Block decomposition approach to compute a minimum geodetic set." RAIRO - Operations Research - Recherche Opérationnelle 48.4 (2014): 497-507. <http://eudml.org/doc/275050>.

@article{Ekim2014,

abstract = {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.},

author = {Ekim, Tınaz, Erey, Aysel},

journal = {RAIRO - Operations Research - Recherche Opérationnelle},

keywords = {convexity; geodetic set; hull set; graph classes},

language = {eng},

number = {4},

pages = {497-507},

publisher = {EDP-Sciences},

title = {Block decomposition approach to compute a minimum geodetic set},

url = {http://eudml.org/doc/275050},

volume = {48},

year = {2014},

}

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

PB - EDP-Sciences

VL - 48

IS - 4

SP - 497

EP - 507

AB - 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.

LA - eng

KW - convexity; geodetic set; hull set; graph classes

UR - http://eudml.org/doc/275050

ER -

## References

top- [1] A.A. Bertossi, Dominating sets for split and bipartite graphs. Inf. Proc. Lett.19 (1984) 37–40. Zbl0539.68058MR761623
- [2] B. Brešar and A. Tepeh Horvat, On the geodetic number of median graphs. Discrete Math.308 (2008) 4044–4051. Zbl1154.05025MR2427737
- [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. Zbl1200.05060MR2459376
- [4] F. Buckley and F. Harary, Geodetic games for graphs. Questiones Math.8 (1986) 321–334. Zbl0615.90093MR854054
- [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. Zbl1207.05043MR2737351
- [6] J. Cáceres, A. Marquez, O. R. Oellerman, M. L. Puertas, Rebuilding convex sets in graphs. Discrete Math.297 (2005) 26–37. Zbl1070.05035MR2159429
- [7] S.R. Canoy, G.B. Cagaanan and S.V. Gervacio, Convexity, Geodetic and Hull Numbers of the Join of Graphs. Utilitas Mathematica71 (2006) 143–159. Zbl1109.05040MR2278828
- [8] G.-B. Chae, E.M. Palmer and W.C. Siu, Geodetic number of random graphs of diameter 2. Aust. J. Combinatorics26 (2002) 11–20. Zbl1012.05059MR1918138
- [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. Zbl1215.05184MR2567969
- [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. Zbl1209.05129MR2574832
- [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. Zbl06051304
- [12] T. Ekim, P. Hell, J. Stacho and D. de Werra, Polar chordal graphs. Discrete Appl. Math.156 (2008) 2469–2479. Zbl1163.05051MR2447022
- [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. Zbl0591.05056MR844046
- [15] O. Gerstel and S. Zaks, A new characterization of tree medians with applications to distributed sorting. Networks24 (1994) 23–29. Zbl0799.90073MR1251706
- [16] A. Hansberg and L. Volkmann, On the geodetic and geodetic domination numbers of a graph. Discrete Math.310 (2010) 2140–2146. Zbl1219.05119MR2651811
- [17] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph. Math. Comput. Modell.17 (1993) 89–95. Zbl0825.68490MR1236514
- [18] T.W. Haynes, M.A. Henning and C. Tiller, Geodetic achievement and avoidance games for graphs. Quaestiones Math.26 (2003) 389–397. Zbl1152.05377MR2046144
- [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. Zbl1062.05052MR2136058
- [20] E. Howorka, A characterization of ptolemaic graphs. J. Graph Theory5 (1981) 323–331. Zbl0437.05046MR625074
- [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. Zbl0313.68032MR396308
- [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. Zbl1303.05195MR3074097
- [23] S.L. Mitchell, Another characterization of the centroid of a tree. Discrete Math.24 (1978) 277–280. Zbl0402.05019MR523317
- [24] H.M. Mulder, The Interval Function of a Graph. Mathematish Centrum, Tract. 132, Amsterdam (1981). Zbl0446.05039MR605838
- [25] M. Necásková, A note on the achievement geodetic games. Questiones Math.12 (1988) 115–119. Zbl0663.90099MR979252
- [26] C. Pandu Rangan, K.R. Parthasarathy and V. Prakash, On the g-centroidal problem in special classes of perfect graphs. Ars Combinatoria50 (1998) 267–278. Zbl0963.05044MR1670577
- [27] F.S. Roberts, Indifference graphs, in Proof techniques in graph theory, edited by F. Harary, Academic Press (1969) 139–146. Zbl0193.24205MR252267
- [28] P. Veeraraghavan, An efficient g-centroid location algorithm for cographs. Inter. J. Math. Math. Sci.9 (2005) 1405–1413. Zbl1076.05076MR2176497
- [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). Zbl0785.52001MR1234493
- [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. Zbl1137.05315MR2256038

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.