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.
Mots-clés : 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 = {https://geodesic-test.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  - https://geodesic-test.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 https://geodesic-test.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. https://geodesic-test.mathdoc.fr/item/DMGT_2004_24_1_a11/

[1] M.J. Atallah, D.Z. Chen, and D.T. Lee, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Algorithmica 14 (1995) 429-441, doi: 10.1007/BF01192049.

[2] M.S. Chang, Efficient algorithms for the domination problems on interval and circular-arc graphs, SIAM J. Comput. 27 (1998) 1671-1694, doi: 10.1137/S0097539792238431.

[3] M.S. Chang, Weighted domination of cocomparability graphs, Discrete Appl. Math. 80 (1997) 135-147, doi: 10.1016/S0166-218X(97)80001-7.

[4] D.Z. Chen, D.T. Lee, R. Sridhar, and C.N. Sekharan, Solving the all-pair shortest path query problem on interval and circular-arc graphs, Networks 31 (1998) 249-258, doi: 10.1002/(SICI)1097-0037(199807)31:4249::AID-NET5>3.0.CO;2-D

[5] E.M. Eschen and J. Spinrad, An O(n²) algorithm for circular-arc graph recognition, in: Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithm SODA'93 (1993) 128-137.

[6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman, San Francisco, CA, 1979).

[7] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980).

[8] M.C. Golumbic and P.L. Hammer, Stability in circular arc graphs, J. Algorithms 9 (1988) 314-320, doi: 10.1016/0196-6774(88)90023-5.

[9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs - Advanced Topics (Marcel Dekker, New York, 1998).

[11] W.L. Hsu, O(M·N) algorithms for the recognization and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24 (1995) 411-439, doi: 10.1137/S0097539793260726.

[12] W.L. Hsu and K.H. Tsai, Linear time algorithms on circular-arc graphs, Inform. Process. Lett. 40 (1991) 123-129, doi: 10.1016/0020-0190(91)90165-E.

[13] J.M. Keil, The complexity of domination problems in circle graphs, Discrete Appl. Math. 42 (1993) 51-63, doi: 10.1016/0166-218X(93)90178-Q.

[14] J.M. Keil and D. Schaefer, An optimal algorithm for finding dominating cycles in circular-arc graphs, Discrete Appl. Math. 36 (1992) 25-34, doi: 10.1016/0166-218X(92)90201-K.

[15] E. Köhler, Connected domination and dominating clique in trapezoid graphs, Discrete Appl. Math. 99 (2000) 91-110, doi: 10.1016/S0166-218X(99)00127-4.

[16] R. Laskar and J. Pfaff, Domination and irredundance in split graphs, Technical Report 430, Dept. Mathematical Sciences (Clemson University, 1983).

[17] C.C. Lee and D.T. Lee, On a circle-cover minimization problem, Inform. Process. Lett. 18 (1984) 109-115, doi: 10.1016/0020-0190(84)90033-4.

[18] Y.L. Lin, F.R. Hsu, and Y.T. Tsai, Efficient algorithms for the minimum connected domination on trapezoid graphs, Lecture Notes in Comput. Sci. 1858 (Springer Verlag, 2000) 126-136.

[19] G.K. Manacher and T.A. Mankus, A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone, Networks 39 (2002) 68-72, doi: 10.1002/net.10014.

[20] S. Masuda and K. Nakajima, An optimal algorithm for finding a maximum independent set of a circular-arc graph, SIAM J. Comput. 17 (1988) 41-52, doi: 10.1137/0217003.

[21] R.M. McConnell, Linear-time recognition of circular-arc graphs, in: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science FOCS'01 (2001) 386-394.

[22] M. Moscarini, Doubly chordal graphs, Steiner trees, and connected domination, Networks 23 (1993) 59-69, doi: 10.1002/net.3230230108.

[23] H. Müller and A. Brandstädt, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theoret. Comput. Sci. 53 (1987) 257-265, doi: 10.1016/0304-3975(87)90067-3.

[24] J. Pfaff, R. Laskar, and S.T. Hedetniemi, NP-completeness of total and connected domination, and irredundance for bipartite graphs, Technical Report 428, Dept. Mathematical Sciences (Clemson University, 1983).

[25] A. Tucker, An efficient test for circular-arc graphs, SIAM J. Comput. 9 (1980) 1-24, doi: 10.1137/0209001.

[26] H.G. Yeh and G.J. Chang, Weighted connected domination and Steiner trees in distance-hereditary graphs, Discrete Appl. Math. 87 (1998) 245-253, doi: 10.1016/S0166-218X(98)00060-2.