A simple linear algorithm for the connected domination problem in circular-arc graphs

Ruo-Wei Hung ; Maw-Shang Chang

Discussiones Mathematicae Graph Theory, Tome 24 (2004), p. 137-145 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2004-01-01

Zbl 1115.05085

EUDML-ID : urn:eudml:doc:270669

Bibliographie

[000] [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. | Zbl 0830.68051

[001] [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. | Zbl 0911.05051

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

[003] [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 | Zbl 1015.68054

[004] [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. | Zbl 0801.68128

[005] [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). | Zbl 0411.68039

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

[007] [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. | Zbl 0651.68083

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

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

[010] [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. | Zbl 0831.68051

[011] [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.

[012] [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. | Zbl 0786.05079

[013] [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. | Zbl 0753.05063

[014] [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. | Zbl 0944.05072

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

[016] [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.

[017] [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. | Zbl 0989.05112

[018] [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. | Zbl 0994.05142

[019] [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. | Zbl 0646.68084

[020] [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.

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

[022] [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. | Zbl 0638.68062

[023] [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).

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

[025] [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. | Zbl 0906.05030