PDF

Discussiones Mathematicae Graph Theory 24(1) (2004) 137-145
DOI: https://doi.org/10.7151/dmgt.1220

A SIMPLE LINEAR ALGORITHM FOR THE CONNECTED DOMINATION PROBLEM IN CIRCULAR-ARC GRAPHS

Ruo-Wei Hung and Maw-Shang Chang

Department of Computer Science and Information Engineering
National Chung Cheng University
Ming-Hsiung, Chiayi 621, Taiwan, R.O.C.
e-mail: {rwhung,mschang}@cs.ccu.edu.tw

Abstract

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.

2000 Mathematics Subject Classification: 05C85, 05C69.

References

[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:4<249::AID-NET5>3.0.CO;2-D.
[5]	E.M. Eschen and J. Spinrad, An O(n2) 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.

Received 18 March 2002
Revised 18 January 2003