@article{, AUTHOR = {Chang, Maw-Shang and Hung, Ruo-Wei}, TITLE = {A simple linear algorithm for the connected domination problem in circular-arc graphs}, JOURNAL = {Discuss. Math. Graph Theory}, FJOURNAL = {Discussiones Mathematicae Graph Theory}, VOLUME = {24}, YEAR = {2004}, NUMBER = {1}, PAGES = {137-145}, ISSN = {1234-3099}, ABSTRACT = {A connected dominating set of a graph $G=(V,E)$ is a subset of
vertices $CD \subseteq 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.}, }
|