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.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.