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

Ruo-Wei Hung; Maw-Shang Chang

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 137-145
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Ruo-Wei Hung, and Maw-Shang Chang. "A simple linear algorithm for the connected domination problem in circular-arc graphs." Discussiones Mathematicae Graph Theory 24.1 (2004): 137-145. <http://eudml.org/doc/270669>.

@article{Ruo2004,
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.},
author = {Ruo-Wei Hung, Maw-Shang Chang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph algorithms; circular-arc graphs; connected dominating set; shortest path},
language = {eng},
number = {1},
pages = {137-145},
title = {A simple linear algorithm for the connected domination problem in circular-arc graphs},
url = {http://eudml.org/doc/270669},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Ruo-Wei Hung
AU - Maw-Shang Chang
TI - A simple linear algorithm for the connected domination problem in circular-arc graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 137
EP - 145
AB - 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.
LA - eng
KW - graph algorithms; circular-arc graphs; connected dominating set; shortest path
UR - http://eudml.org/doc/270669
ER -

References

top
  1. [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. Zbl0830.68051
  2. [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. Zbl0911.05051
  3. [3] M.S. Chang, Weighted domination of cocomparability graphs, Discrete Appl. Math. 80 (1997) 135-147, doi: 10.1016/S0166-218X(97)80001-7. Zbl0898.05077
  4. [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 Zbl1015.68054
  5. [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. Zbl0801.68128
  6. [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). Zbl0411.68039
  7. [7] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
  8. [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. Zbl0651.68083
  9. [9] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  10. [10] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs - Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
  11. [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. Zbl0831.68051
  12. [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. [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. Zbl0786.05079
  14. [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. Zbl0753.05063
  15. [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. Zbl0944.05072
  16. [16] R. Laskar and J. Pfaff, Domination and irredundance in split graphs, Technical Report 430, Dept. Mathematical Sciences (Clemson University, 1983). 
  17. [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. [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. Zbl0989.05112
  19. [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. Zbl0994.05142
  20. [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. Zbl0646.68084
  21. [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. [22] M. Moscarini, Doubly chordal graphs, Steiner trees, and connected domination, Networks 23 (1993) 59-69, doi: 10.1002/net.3230230108. Zbl0771.05076
  23. [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. Zbl0638.68062
  24. [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. [25] A. Tucker, An efficient test for circular-arc graphs, SIAM J. Comput. 9 (1980) 1-24, doi: 10.1137/0209001. Zbl0453.05054
  26. [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. Zbl0906.05030

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.