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.
Mots-clés : 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://www.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://www.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://www.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, Tome 48 (2014) no. 4, pp. 497-507. doi : 10.1051/ro/2014019. http://www.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] and , On the geodetic number of median graphs. Discrete Math. 308 (2008) 4044-4051. | MR | Zbl
[3] , and , On the geodetic number and related metric sets in Cartesian product graphs. Discrete Math. 308 (2008) 5555-5561. | MR | Zbl
[4] and , Geodetic games for graphs. Questiones Math. 8 (1986) 321-334. | MR | Zbl
[5] , , , and , On the geodetic and the hull numbers in strong product graphs. Comput. Math. Appl. 60 (2010) 3020-3031. | MR | Zbl
[6] , , , , Rebuilding convex sets in graphs. Discrete Math. 297 (2005) 26-37. | MR | Zbl
[7] , and , Convexity, Geodetic and Hull Numbers of the Join of Graphs. Utilitas Mathematica 71 (2006) 143-159. | MR | Zbl
[8] , and , Geodetic number of random graphs of diameter 2. Aust. J. Combinatorics 26 (2002) 11-20. | MR | Zbl
[9] , , , and , On the computation of the hull number of a graph. Discrete Math. 309 (2009) 5668-5674. | MR | Zbl
[10] , , and , 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] , , and , Polar chordal graphs. Discrete Appl. Math. 156 (2008) 2469-2479. | MR | Zbl
[13] , Convexity in graphs. Master's Thesis, Boğaziçi University (2011).
[14] and , Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Meth. 7 (1986) 433-442. | MR | Zbl
[15] and , A new characterization of tree medians with applications to distributed sorting. Networks 24 (1994) 23-29. | MR | Zbl
[16] and , On the geodetic and geodetic domination numbers of a graph. Discrete Math. 310 (2010) 2140-2146. | MR | Zbl
[17] , and , The geodetic number of a graph. Math. Comput. Modell. 17 (1993) 89-95. | MR | Zbl
[18] , and , Geodetic achievement and avoidance games for graphs. Quaestiones Math. 26 (2003) 389-397. | MR | Zbl
[19] , , , and , On the Steiner, geodetic and hull numbers of graphs Discrete Math. 293 (2005) 139-154. | MR | Zbl
[20] , A characterization of ptolemaic graphs. J. Graph Theory 5 (1981) 323-331. | MR | Zbl
[21] and , Some properties of a centroid of a free tree. Inf. Process. Lett. 4 (1975) 18-20. | MR | Zbl
[22] and , 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] , 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] , and , On the g-centroidal problem in special classes of perfect graphs. Ars Combinatoria 50 (1998) 267-278. | MR | Zbl
[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] , and , The lower and upper forcing geodetic numbers of block-cactus graphs. Eur. J. Oper. Res. 175 (2006) 238-245. | MR | Zbl
Cité par Sources :
