Abstract
It is shown in this paper that the weighted domination problem and its two variants, the weighted connected domination and weighted total domination problems are NP-complete on cocomparability graphs when arbitrary integer vertex weights are allowed and all of them can be solved in polynomial time if vertex weights are integers and less than or equal to a constant c. Besides, an O(¦V¦2) algorithm is given for the weighted independent perfect domination problem of a cocomparability graph G=(V, E).
Supported partly by the National Science Council of the Republic of China under grant NSC 85-2121-M-194-020.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
D. W. Bange, A. E. Barkauskas, and P. T. Slater, Efficient dominating sets in graphs, Applications of Discrete Mathematics, R. D. Ringeisen and F. S. Roberts, eds., SIAM, Philad. (1988)189–199.
G. J. Chang, Private communication.
G. J. Chang, C. Pandu Rangan and S. R. Coorg, Weighted independent perfect domination on cocomparability graphs, Lecture Notes in Computer Science, Vol. 766, Springer-Verlag, (1993) 506–514.
M. S. Chang and Y. C. Liu, Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs, Information Process. Lett. 48 (1993) 205–210.
D. G. Corneil and L. Stewart, Dominating sets in perfect graphs, Discrete Math. 86 (1990) 145–164.
P. Damaschke, J. S. Deogun, D. Kratsch and G. Steiner, Finding Hamiltonian paths in cocomparability graphs using bump number algorithm, Order 8 (1992) 383–391.
J. S. Deogun and G. Steiner, Hamiltonian cycle is polynomial on cocomparability graphs, Discrete Appl. Math. 39 (1992) 165–172.
J. S. Deogun and G. Steiner, Polynomial algorithms for Hamiltonian cycle in cocomparability graphs, SIAM J. Comput., to appear.
M. Farber, Independent domination in chordal graphs, Operations Research Lett. 4 (1982) 134–138.
M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, (1979) W. H. Freeman, New York.
D. Kratsch and L. Stewart, Domination on cocomparability graphs, SIAM J. Disc. Math. 6 (1993), 400–417.
R. M. McConnell and J. P. Spinrad, Linear time modular decomposition and efficient transitive orientation of comparability graphs, Proc. of the fifth annual ACM-SIAM symposium on discrete algorithms (1994) 536–545.
G. K. Manacher and T. A. Mankus, Incorporating negative-weight vertices in certain vertex-search graph algorithms, Information Process. Lett., 42 (1992) 293–294.
R. Sedgewick, Algorithms, Addison-Wesley Publishing Company, Massachusetts (1983).
J. Spinrad, On comparability and permutation graphs, SIAM J. Comput. 14 (1985) 658–670.
C. C. Yen and R. C. T. Lee, The weighted perfect domination problem, Inform. Processing Letters 35 (1990) 295–299.
C. C. Yen and R. C. T. Lee, The weighted perfect domination problem and its variants, manuscript.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chang, MS. (1995). Weighted domination on cocomparability graphs. In: Staples, J., Eades, P., Katoh, N., Moffat, A. (eds) Algorithms and Computations. ISAAC 1995. Lecture Notes in Computer Science, vol 1004. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015415
Download citation
DOI: https://doi.org/10.1007/BFb0015415
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60573-7
Online ISBN: 978-3-540-47766-2
eBook Packages: Springer Book Archive