Geodesic
Block decomposition approach to compute a minimum geodetic set
RAIRO - Operations Research - Recherche Opérationnelle, Tome 48 (2014) no. 4, pp. 497-507 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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.

DOI : 10.1051/ro/2014019
Classification : 05C12, 05C85
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},
     year = {2014},
     publisher = {EDP-Sciences},
     volume = {48},
     number = {4},
     doi = {10.1051/ro/2014019},
     mrnumber = {3264390},
     zbl = {1301.05100},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :