Block decomposition approach to compute a minimum geodetic set

Tınaz Ekim; Aysel Erey

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

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

Abstract

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

How to cite

top

Ekim, 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. [1] A.A. Bertossi, Dominating sets for split and bipartite graphs. Inf. Proc. Lett.19 (1984) 37–40. Zbl0539.68058MR761623
  2. [2] B. Brešar and A. Tepeh Horvat, On the geodetic number of median graphs. Discrete Math.308 (2008) 4044–4051. Zbl1154.05025MR2427737
  3. [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. [4] F. Buckley and F. Harary, Geodetic games for graphs. Questiones Math.8 (1986) 321–334. Zbl0615.90093MR854054
  5. [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. [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. [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. [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. [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. [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. [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. [12] T. Ekim, P. Hell, J. Stacho and D. de Werra, Polar chordal graphs. Discrete Appl. Math.156 (2008) 2469–2479. Zbl1163.05051MR2447022
  13. [13] A. Erey, Convexity in graphs. Master’s Thesis, Boğaziçi University (2011). 
  14. [14] M. Farber and R.E. Jamison, Convexity in graphs and hypergraphs. SIAM J. Algebraic Discrete Meth.7 (1986) 433–442. Zbl0591.05056MR844046
  15. [15] O. Gerstel and S. Zaks, A new characterization of tree medians with applications to distributed sorting. Networks24 (1994) 23–29. Zbl0799.90073MR1251706
  16. [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. [17] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph. Math. Comput. Modell.17 (1993) 89–95. Zbl0825.68490MR1236514
  18. [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. [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. [20] E. Howorka, A characterization of ptolemaic graphs. J. Graph Theory5 (1981) 323–331. Zbl0437.05046MR625074
  21. [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. [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. [23] S.L. Mitchell, Another characterization of the centroid of a tree. Discrete Math.24 (1978) 277–280. Zbl0402.05019MR523317
  24. [24] H.M. Mulder, The Interval Function of a Graph. Mathematish Centrum, Tract. 132, Amsterdam (1981). Zbl0446.05039MR605838
  25. [25] M. Necásková, A note on the achievement geodetic games. Questiones Math.12 (1988) 115–119. Zbl0663.90099MR979252
  26. [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. [27] F.S. Roberts, Indifference graphs, in Proof techniques in graph theory, edited by F. Harary, Academic Press (1969) 139–146. Zbl0193.24205MR252267
  28. [28] P. Veeraraghavan, An efficient g-centroid location algorithm for cographs. Inter. J. Math. Math. Sci.9 (2005) 1405–1413. Zbl1076.05076MR2176497
  29. [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. [30] M.J.L. van de Vel, Theory of convex structures. North-Holland (1993). Zbl0785.52001MR1234493
  31. [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 ?

top

You must be logged in to post comments.