Geodesic
A simple linear algorithm for the connected domination problem in circular-arc graphs
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 1, pp. 137-145

Voir la notice de l'article provenant de la source Library of Science

A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
Keywords: graph algorithms, circular-arc graphs, connected dominating set, shortest path 
@article{DMGT_2004_24_1_a11,
     author = {Hung, Ruo-Wei and Chang, Maw-Shang},
     title = {A simple linear algorithm for the connected domination problem in circular-arc graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {137--145},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a11/}
}
TY  - JOUR
AU  - Hung, Ruo-Wei
AU  - Chang, Maw-Shang
TI  - A simple linear algorithm for the connected domination problem in circular-arc graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 137
EP  - 145
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a11/
LA  - en
ID  - DMGT_2004_24_1_a11
ER  - 
%0 Journal Article
%A Hung, Ruo-Wei
%A Chang, Maw-Shang
%T A simple linear algorithm for the connected domination problem in circular-arc graphs
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 137-145
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a11/
%G en
%F DMGT_2004_24_1_a11
Hung, Ruo-Wei; Chang, Maw-Shang. A simple linear algorithm for the connected domination problem in circular-arc graphs. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 1, pp. 137-145. http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a11/