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/