Abstract
Given the trapezoid diagram, the problem of finding the minimum cardinality connected dominating set in trapezoid graphs was solved in O(m+ n) time [7]; the results is recently improved to be O(n) time by Kohler [5]. For the (vertex) weighted case, finding the minimum weighted connected dominating set in trapezoid graphs can be solved in O(m + n log n) time [11]. Here n (m) denotes the number of vertices (edges) of the trapezoid graph.
In this paper, we show a different approach for finding the minimum cardinality connected dominating set in trapezoid graphs using O(n) time. For finding the minimum weighted connected dominating set, we show the problem can be efficiently solved in O(n log log n) time.
The work was partly supported by the National Science Council, Taiwan, R.O.C, grant NSC-88-2213-E-126-005.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. Graph Classes: A Survey. SIAM monographs on discrete mathematics and applications, Philadelphia, P. A., 1999.
M.-S. Chang. Weighted domination of cocomparability graphs. Discr. Applied Math., 80:135–148, 1997.
I. Dagan, M.C. Golumbic, and R.Y. Pinter. Trapezoid graphs and their coloring. Discr. Applied Math., 21:35–46, 1988.
T.W. Haynes, S.T. Hedetniemi, and P.J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., N. Y., 1998.
E. Kohler. Connected domination and dominating clique in trapezoid graphs. Discr. Applied Math., 99:91–110, 2000.
D. Kratsch and L. K. Stewart. Domination on cocomparability graphs. SIAM J. Discrete Math., 6(3):400–417, 1993.
Y. D. Liang. Steiner set and connected domination in trapezoid graphs. Information Processing Letters, 56(2):101–108, 1995.
Y. Daniel Liang. Dominations in trapezoid graphs. Information Processing Letters, 52(6):309–315, December 1994.
Yaw-Ling Lin. Fast algorithms for independent domination and efficient domination in trapezoid graphs. In ISAAC’98, LNCS 1533, pages 267–276, Taejon, Korea, December 1998. Springer-Verlag.
T.-H. Ma and J.P. Spinrad. On the 2-chain subgraph cover and related problems. J. Algorithms, 17:251–268, 1994.
Anand Srinivasan, M.S. Chang, K. Madhukar, and C. Pandu Rangan. Efficient algorithms for the weighted domination problems on trapezoid graphs. Manuscript, 1996.
P. van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6:80–82, 1977.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lin, YL., Hsu, F.R., Tsai, YT. (2000). Efficient Algorithms for the Minimum Connected Domination on Trapezoid Graphs. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_13
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive