A polynomial-time algorithm for the paired-domination problem on permutation graphs. (English) Zbl 1168.05366
Summary: A set \(S\) of vertices in a graph \(H=(V,E)\) with no isolated vertices is a paired-dominating set of \(H\) if every vertex of \(H\) is adjacent to at least one vertex in \(S\) and if the subgraph induced by \(S\) contains a perfect matching. Let \(G\) be a permutation graph and \(\pi \) be its corresponding permutation. In this paper we present an \(O(mn)\) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph \(G\) with \(n\) vertices and \(m\) edges.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | Arvind, K.; Regan, C. P., Connected domination and steiner set on weighted permutation graphs, Information Processing Letters, 41, 215-220 (1992) · Zbl 0754.68060 |
| [2] | Blidia, M.; Chellali, M.; Haynes, T. W., Characterizations of trees with equal paired and double domination numbers, Discrete Mathematics, 306, 1840-1845 (2006) · Zbl 1100.05068 |
| [3] | Brešar, B.; Henning, M. A.; Rall, D. F., Paired-domination of Cartesian products of graphs and rainbow domination, Electronic Notes in Discrete Mathematics, 22, 233-237 (2005) · Zbl 1200.05154 |
| [4] | Brešar, B.; Klavžar, S.; Rall, D. F., Dominating direct products of graphs, Discrete Mathematics, 307, 1636-1642 (2007) · Zbl 1116.05055 |
| [5] | Chang, G. J., Algorithmic aspects of domination in graphs, (Du, D.-Z.; Pardalos, P. M., Handbook of Combinatorial Optimization, vol. 3 (1998), Kluwer Academic Pub: Kluwer Academic Pub Boston), 339-405 · Zbl 1058.90524 |
| [6] | Chao, H. S.; Hsu, F. R.; Lee, R. C.T., An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Discrete Applied Mathematics, 102, 159-173 (2000) · Zbl 1052.90095 |
| [7] | Chellali, M.; Haynes, T. W., Total and paired-domination numbers of a tree, AKCE International Journal of Graphs and Combinatorics, 1, 69-75 (2004) · Zbl 1066.05101 |
| [8] | Cheng, T. C.E.; Kang, L. Y.; Ng, C. T., Paired domination on interval and circular-arc graphs, Discrete Applied Mathematics, 155, 2077-2086 (2007) · Zbl 1124.05070 |
| [9] | Farber, M.; Keil, J. M., Domination in permutation graphs, Journal of Algorithms, 6, 309-321 (1985) · Zbl 0598.05056 |
| [10] | Favaron, O.; Henning, M. A., Paired-domination in claw-free cubic graphs, Graphs and Combinatorics, 20, 447-456 (2004) · Zbl 1054.05074 |
| [11] | Fitzpatrick, S.; Hartnell, B., Paired-domination, Discussiones Mathematicae. Discussiones Mathematicae, Graph Theory, 18, 63-72 (1998) · Zbl 0916.05061 |
| [12] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 |
| [13] | Haynes, T. W.; Slater, P. J., Paired-domination in graphs, Networks, 32, 199-206 (1998) · Zbl 0997.05074 |
| [14] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamendals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [15] | Haynes, T. W.; Henning, M. A., Trees with large paired-domination number, Utilitas Mathematica, 71, 3-12 (2006) · Zbl 1112.05078 |
| [16] | Haynes, T. W.; Henning, M. A.; Slater, P. J., Trees with equal domination and paired-domination numbers, Ars Combinatoria, 76, 169-175 (2005) · Zbl 1164.05420 |
| [17] | Henning, M. A., Trees with equal total domination and paired-domination numbers, Utilitas Mathematica, 69, 207-218 (2006) · Zbl 1100.05070 |
| [18] | Henning, M. A., Graphs with large paired-domination number, Journal of Combinatorial Optimization, 13, 61-78 (2007) · Zbl 1108.05069 |
| [19] | Henning, M. A.; Plummer, M. D., Vertices contained in all or in no minimum paired- dominating set of a tree, Journal of Combinatorial Optimization, 10, 283-294 (2005) · Zbl 1122.05071 |
| [20] | Ibarra, O. H.; Zhang, Q., Some efficient algorithms for permutation graphs, Journal of Algorithms, 16, 453-469 (1994) · Zbl 0804.68102 |
| [21] | Kang, L. Y.; Sohn, M. Y.; Cheng, T. C.E., Paired-domination in inflated graphs, Theoretical Computer Science, 320, 485-494 (2004) · Zbl 1051.05067 |
| [22] | Kratsch, D.; McConnell, R. M.; Mehlhorn, K.; Spinrad, J. P., Certifying algorithms for recognizing interval graphs and permutation graphs, SIAM Journal on Computing, 36, 326-353 (2006) · Zbl 1113.68112 |
| [23] | Liang, Y.; Rhee, C.; Dhall, S. K.; Lakshmivarahan, S., A new approach for the domination problem on permutation graphs, Information Processing Letters, 37, 219-224 (1991) · Zbl 0713.68038 |
| [24] | Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Canadian Journal of Mathematics, 23, 160-175 (1971) · Zbl 0204.24604 |
| [25] | Proffitt, K. E.; Haynes, T. W.; Slater, P. J., Paired-domination in grid graphs, Congressus Numerantium, 150, 161-172 (2001) · Zbl 0988.05067 |
| [26] | Qiao, H.; Kang, L. Y.; Cardei, M.; Du, D. Z., Paired-domination of trees, Journal of Global Optimization, 25, 43-54 (2003) · Zbl 1013.05055 |
| [27] | Raczek, J., Lower bound on the paired domination number of a tree, The Australasian Journal of Combinatorics, 34, 343-347 (2006) · Zbl 1105.05054 |
| [28] | Saha, A.; Pal, M.; Pal, T. K., An efficient PRAM algorithm for maximum-weight independent set on permutation graphs, Journal of Applied Mathematics & Computing, 19, 77-92 (2005) · Zbl 1082.05089 |
| [29] | Shan, E. F.; Kang, L. Y.; Henning, M. A., A characterization of trees with equal total domination and paired-domination numbers, Australasian Journal of Combinatorics, 30, 31-39 (2004) · Zbl 1054.05081 |
| [30] | Spinrad, J., On comparability and permutation graphs, SIAM Journal on Computing, 14, 658-670 (1985) · Zbl 0568.68051 |
| [31] | Tsai, K. H.; Hsu, W. L., Fast algorithms for the dominating set problem on permutation graphs, Algorithmica, 9, 601-614 (1993) · Zbl 0768.68063 |
| [32] | Xu, G. J.; Kang, L. Y.; Shan, E. F., Acyclic domination on bipartite permutation graphs, Information Processing Letters, 99, 139-144 (2006) · Zbl 1184.05092 |
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.
