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.

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] Dominating sets for split and bipartite graphs. Inf. Proc. Lett. 19 (1984) 37-40. | MR | Zbl

,[2] On the geodetic number of median graphs. Discrete Math. 308 (2008) 4044-4051. | MR | Zbl

and ,[3] On the geodetic number and related metric sets in Cartesian product graphs. Discrete Math. 308 (2008) 5555-5561. | MR | Zbl

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

and ,[5] On the geodetic and the hull numbers in strong product graphs. Comput. Math. Appl. 60 (2010) 3020-3031. | MR | Zbl

, , , and ,[6] Rebuilding convex sets in graphs. Discrete Math. 297 (2005) 26-37. | MR | Zbl

, , , ,[7] Convexity, Geodetic and Hull Numbers of the Join of Graphs. Utilitas Mathematica 71 (2006) 143-159. | MR | Zbl

, and ,[8] Geodetic number of random graphs of diameter 2. Aust. J. Combinatorics 26 (2002) 11-20. | MR | Zbl

, and ,[9] On the computation of the hull number of a graph. Discrete Math. 309 (2009) 5668-5674. | MR | Zbl

, , , and ,[10] Some remarks on the geodetic number of a graph. Discrete Math. 310 (2010) 832-837. | MR | Zbl

, , and ,[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] Polar chordal graphs. Discrete Appl. Math. 156 (2008) 2469-2479. | MR | Zbl

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

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

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

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

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

, and ,[18] Geodetic achievement and avoidance games for graphs. Quaestiones Math. 26 (2003) 389-397. | MR | Zbl

, and ,[19] On the Steiner, geodetic and hull numbers of graphs Discrete Math. 293 (2005) 139-154. | MR | Zbl

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

,[21] Some properties of a centroid of a free tree. Inf. Process. Lett. 4 (1975) 18-20. | MR | Zbl

and ,[22] 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

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

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

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

,[26] On the g-centroidal problem in special classes of perfect graphs. Ars Combinatoria 50 (1998) 267-278. | MR | Zbl

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

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

,[29] 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] Theory of convex structures. North-Holland (1993). | MR | Zbl

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

, and ,*Cited by Sources: *