Linear-time algorithm for the matched-domination problem in cographs. (English) Zbl 1232.05166
Summary: Let \(G=(V, E)\) be a graph without isolated vertices. A matching in \(G\) is a set of independent edges in \(G\). A perfect matching \(M\) in \(G\) is a matching such that every vertex of \(G\) is incident to an edge of \(M\). A set \(S \subseteq V\) is a paired-dominating set of \(G\) if every vertex not in \(S\) is adjacent to a vertex in \(S\) and if the subgraph induced by \(S\) contains a perfect matching. The paired-domination problem is to find a paired-dominating set of \(G\) with minimum cardinality. This paper introduces a generalization of the paired-domination problem, namely, the matched-domination problem, in which some constrained vertices are in paired-dominating sets as far as they can. Further, possible applications are also presented. We then present a linear-time constructive algorithm to solve the matched-domination problem in cographs.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | DOI: 10.1016/0095-8956(86)90043-2 · Zbl 0605.05024 · doi:10.1016/0095-8956(86)90043-2 |
| [2] | DOI: 10.1016/0020-0190(89)90221-4 · Zbl 0684.68046 · doi:10.1016/0020-0190(89)90221-4 |
| [3] | DOI: 10.1137/0406014 · Zbl 0773.05091 · doi:10.1137/0406014 |
| [4] | Chang, M. S., Hsieh, S. Y. and Chen, G. H. 1997.Dynamic Programming on Distance-Hereditary Graphs, Vol. 1350, 344–353. Berlin: Springer. Lecture Notes in Computer Science |
| [5] | DOI: 10.1016/j.laa.2008.03.016 · Zbl 1149.05032 · doi:10.1016/j.laa.2008.03.016 |
| [6] | DOI: 10.1007/s10878-008-9177-6 · Zbl 1197.90336 · doi:10.1007/s10878-008-9177-6 |
| [7] | DOI: 10.1016/j.dam.2007.05.011 · Zbl 1124.05070 · doi:10.1016/j.dam.2007.05.011 |
| [8] | DOI: 10.1016/j.dam.2008.02.015 · Zbl 1168.05366 · doi:10.1016/j.dam.2008.02.015 |
| [9] | DOI: 10.1016/0166-218X(81)90013-5 · Zbl 0463.05057 · doi:10.1016/0166-218X(81)90013-5 |
| [10] | DOI: 10.1137/0214065 · Zbl 0575.68065 · doi:10.1137/0214065 |
| [11] | DOI: 10.1016/S0304-3975(00)00234-6 · Zbl 0972.05046 · doi:10.1016/S0304-3975(00)00234-6 |
| [12] | DOI: 10.1016/j.dam.2004.01.011 · Zbl 1055.05107 · doi:10.1016/j.dam.2004.01.011 |
| [13] | DOI: 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F · Zbl 0997.05074 · doi:10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F |
| [14] | Haynes T. W., Fundamentals of Domination in Graphs (1998) · Zbl 0890.05002 |
| [15] | Haynes T. W., Domination in Graphs: Advanced Topics (1998) · Zbl 0883.00011 |
| [16] | DOI: 10.1016/j.aml.2006.05.003 · Zbl 1123.05055 · doi:10.1016/j.aml.2006.05.003 |
| [17] | Hung, R. W. 2006.A linear-time algorithm for the terminal path cover problem in cographs. Proceedings of the 23rd Workshop on Combinatorial Mathematics and Computation Theory. 2006, Changhwa, Taiwan. pp.62–75. Available athttp://algo2006.csie.dyu.edu.tw/paper/1/B14.pdf |
| [18] | DOI: 10.1016/j.disc.2003.10.023 · Zbl 1042.05074 · doi:10.1016/j.disc.2003.10.023 |
| [19] | Lerchs, H. 1971. ”On cliques and kernels”. Toronto: Department of Computer Science, University of Toronto. Tech. Rep |
| [20] | DOI: 10.1016/S0304-3975(02)00068-3 · Zbl 1038.68087 · doi:10.1016/S0304-3975(02)00068-3 |
| [21] | DOI: 10.1016/j.dam.2005.02.004 · Zbl 1101.68108 · doi:10.1016/j.dam.2005.02.004 |
| [22] | DOI: 10.1023/A:1021338214295 · Zbl 1013.05055 · doi:10.1023/A:1021338214295 |
| [23] | DOI: 10.1016/S0304-3975(01)00175-X · Zbl 1028.68154 · doi:10.1016/S0304-3975(01)00175-X |
| [24] | DOI: 10.1016/S0166-218X(03)00448-7 · Zbl 1062.68092 · doi:10.1016/S0166-218X(03)00448-7 |
| [25] | DOI: 10.1016/0020-0190(93)90230-7 · Zbl 0776.68063 · doi:10.1016/0020-0190(93)90230-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
