×

Dominating sets in perfect graphs. (English) Zbl 0746.05066

Summary: We review the complexity of the minimum cardinality dominating set problem and some of its variations on several families of perfect graphs. We describe the techniques which are used to attain these complexity results, with emphasis on the dynamic programming approach to the design of algorithms.

MSC:

05C99 Graph theory
68R10 Graph theory (including graph drawing) in computer science
05C85 Graph algorithms (graph-theoretic aspects)
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Appl. Math., 23, 11-24 (1989) · Zbl 0666.68067
[2] Berge, C., Farbung von Graphen deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin Luther Univ. Halle Wittenberg Math-Natur. Reihe, 114 (1961)
[3] Berge, C.; Duchet, P., Strongly perfect graphs, Ann. Discrete Math., 21, 57-61 (1984) · Zbl 0558.05037
[4] Bertossi, A. A., Dominating sets for split and bipartite graphs, Inform. Process. Lett., 19, 37-40 (1984) · Zbl 0539.68058
[5] Bertossi, A. A., Total domination in interval graphs, Inform. Process. Lett., 23, 131-134 (1986) · Zbl 0604.05032
[6] Bertossi, A. A.; Bonuccelli, M. A., Hamiltonian circuits in interval graph generalizations, Inform. Process. Lett., 23, 195-200 (1986) · Zbl 0627.68056
[7] Beyer, T.; Proskurowski, A.; Hedetniemi, S.; Mitchell, S., Independent domination in trees, (Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and computing (1977), Utilitas Mathematica: Utilitas Mathematica Winnipeg), 321-328 · Zbl 0417.05020
[8] Booth, K. S., Dominating sets in chordal graphs, (Research Report CS-80-34 (1980), University of Waterloo) · Zbl 0485.05055
[9] Booth, K. S.; Johnson, J. H., Dominating sets in chordal graphs, SIAM J. Comput., 11, 191-199 (1982) · Zbl 0485.05055
[10] Brandstadt, A.; Kratsch, D., On the restriction of some NP-complete problems to permutation graphs, (Technical Report N/84/80 (1984), Sektion Mathematik der Friedrich-Schiller-Universitat Jena) · Zbl 0565.05060
[11] Brandstadt, A.; Kratsch, D., On the restriction of some NP-complete problems to permutation graphs, (Proceedings of FCT’85. Proceedings of FCT’85, Lecture Notes in Computer Science, 199 (1985), Springer: Springer Berlin), 53-62, (extended abstract of [10])
[12] Brandstadt, A.; Kratsch, D., On domination problems for permutation and other graphs, Theoret. Comput. Sci., 54, 181-198 (1987) · Zbl 0641.68100
[13] Burlet, M.; Uhry, J. P., Parity graphs, Ann. Discrete Math., 21, 253-277 (1984) · Zbl 0558.05036
[14] Chvatal, V., Perfectly ordered graphs, Ann. Discrete Math., 21, 63-65 (1984) · Zbl 0559.05055
[15] Cockayne, E. J.; Goodman, S.; Hedetniemi, S. T., A linear algorithm for the domination number of a tree, Inform. Process. Lett., 4, 41-44 (1975) · Zbl 0311.68024
[16] Colbourn, C. J.; Keil, J. M.; Stewart, L. K., Finding minimum dominating cycles in permutation graphs, Oper. Res. Lett., 4, 13-17 (1985) · Zbl 0569.90091
[17] Colbourn, C. J.; Stewart, L. K., Dominating cycles in series-parallel graphs, Ars Combin., 19A, 107-112 (1985) · Zbl 0568.05035
[18] Colbourn, C. J.; Stewart, L. K., Permutation graphs; connected domination and Steiner trees, (Research Report CCS-85-02 (1985), Faculty of Mathematics, University of Waterloo), to appear in Ann. Discrete Math. · Zbl 0744.05059
[19] Corneil, D. G.; Kirkpatrick, D. G., Families of recursively defined perfect graphs, Proceedings of the Fourteenth Southeastern Conference on Combinatorics. Proceedings of the Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, 237-246 (1983) · Zbl 0576.05023
[20] Corneil, D. G.; Perl, Y., Clustering and domination in perfect graphs, Discrete Appl. Math., 9, 27-39 (1984) · Zbl 0581.05053
[21] Corneil, D. G.; Keil, J. M., A dynamic programming approach to the dominating set problem on \(k\)-trees, SIAM J. Algebraic Discrete Methods, 8, 535-543 (1987) · Zbl 0635.05040
[22] Dewdney, A. K., Fast Turing reductions between problems in NP 4, (Report, 71 (1981), University of Western Ontario) · Zbl 0960.68500
[23] Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. ACM, 19, 400-410 (1972) · Zbl 0251.05113
[24] Farber, M., Independent domination in chordal graphs, Oper. Res. Lett., 1, 134-138 (1982) · Zbl 0495.05053
[25] Farber, M., Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math., 7, 115-130 (1984) · Zbl 0531.05045
[26] Farber, M.; Keil, J. M., Domination in permutation graphs, J. Algorithms, 6, 309-321 (1985) · Zbl 0598.05056
[27] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[28] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[29] Hayward, R. B., Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 200-209 (1985) · Zbl 0551.05055
[30] Johnson, D. S., The NP-completeness column: an ongoing guide, J. Algorithms, 6, 434-451 (1985) · Zbl 0608.68032
[31] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-103 · Zbl 0366.68041
[32] Keil, J. M., Total domination in interval graphs, Inform. Process. Lett., 22, 171-174 (1986) · Zbl 0595.05063
[33] J.M. Keil, private communication, 1986.; J.M. Keil, private communication, 1986.
[34] J.M. Keil, private communication, 1987.; J.M. Keil, private communication, 1987.
[35] Laskar, R.; Pfaff, J., Domination and irredundance in split graphs, (Technical Report, 430 (1983), Clemson University) · Zbl 0647.05060
[36] Laskar, R.; Pfaff, J.; Hedetniemi, S. M.; Hedetniemi, S. T., On the algorithm complexity of total domination, SIAM J. Algebraic and Discrete Methods, 5, 420-425 (1984) · Zbl 0576.68056
[37] Meyniel, H., The graphs whose odd cycles have at least two chords, Ann. Discrete Math., 21, 115-119 (1984) · Zbl 0567.05034
[38] Pfaff, J.; Laskar, R.; Hedetniemi, S. T., NP-completeness of total and connected domination and irredundance for bipartite graphs, (Technical Report, 428 (1983), Clemson University) · Zbl 0647.05060
[39] Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23, 160-175 (1971) · Zbl 0204.24604
[40] Ramalingam, G.; Rangan, C. P., A unified approach to domination problems on iterval graphs, Inform. Process. Lett., 27, 271-274 (1988) · Zbl 0658.05040
[41] Spinrad, J., Transitive orientation in \(O(n^2)\) time, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 457-466 (1983)
[42] White, K.; Farber, M.; Pulleyblank, W. R., Steiner trees, connected domination, and strongly chordal graphs, Networks, 15, 109-124 (1985) · Zbl 0579.05050
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.