×

Domination, independent domination, and duality in strongly chordal graphs. (English) Zbl 0531.05045

Polynomial-time algorithms for finding minimum weight dominating sets and independent dominating sets in strongly chordal graphs are presented in this paper. The algorithms are based on linear programming formulations of the problems and consist of two stages: in the first - a greedy algorithm is used to solve the corresponding dual program, and in the second - feasible solution to the primal is read off. In the second part, a relationship between strongly chordal graphs and totally balanced matrices is utilized to show that the domatic number achieves its theoretical lower bound in strongly chordal graphs and to efficiently solve certain optimization problems for totally balanced matrices.
Reviewer: M.M.Sysło

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms, to appear.; R.P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms, to appear.
[2] Berge, C., Balanced matrices, Math. Programming, 2, 19-31 (1972) · Zbl 0247.05126
[3] Beyer, T.; Proskurowski, A.; Hedetniemi, S.; Michell, S., Independent domination in trees, (Proc. Eighth Southeastern Conf. Combinatorics, Graph Theory, and Computing (1977), Utilitas Math: Utilitas Math Winnipeg), 321-328 · Zbl 0417.05020
[4] Booth, K. S.; Johnson, J. H., Dominating sets in chordal graphs, SIAM J. Comput., 11, 191-199 (1982) · Zbl 0485.05055
[5] G.J. Chang, Private communication, 1982.; G.J. Chang, Private communication, 1982.
[6] Chang, G. J.; Nemhauser, G. L., The \(k\)-domination and \(k\)-stability problems on graphs, (T.R. 540 (1982), School of OR/IE, Cornell University) · Zbl 0576.05054
[7] Cockayne, E.; Goodman, S.; Hedetniemi, S., A linear algorithm for the domination number of a tree, Inform. Process. Letters, 4, 41-44 (1975) · Zbl 0311.68024
[8] Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 247-261 (1977) · Zbl 0384.05051
[9] Farber, M., Domination and duality in weighted trees, (Proc. Twelfth Southeastern Conf. Combinatorics, Graph Theory, and Computing (1982), Utilitas Math: Utilitas Math Winnipeg) · Zbl 0498.05025
[10] Farber, M., Applications of 1.p. duality to problems involving independence and domination, (Technical Report 81-13 (1981), Computing Science Department, Simon Fraser University), also issued as · JFM 56.0042.02
[11] Farber, M., Independent domination in chordal graphs, Operations Research Letters, 1, 134-138 (1982) · Zbl 0495.05053
[12] Farber, M., Characterizations of strongly chordal graphs, Discrete Math., 43, 173-189 (1983) · Zbl 0514.05048
[13] Fulkerson, D. R.; Hoffman, A. J.; Oppenheim, R., On balanced matrices, Math. Programming Study, 1, 120-132 (1974) · Zbl 0357.90038
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[15] A.J. Hoffman, A.W.J. Kolen and M. Sakarovitch, Totally-balanced and greedy matrices, submitted to SIAM J. Algebraic Discrete Methods.; A.J. Hoffman, A.W.J. Kolen and M. Sakarovitch, Totally-balanced and greedy matrices, submitted to SIAM J. Algebraic Discrete Methods. · Zbl 0573.05041
[16] Khachian, L. G., A polynomial algorithm in linear programming, Soviet Math. Dokl., 20, 191-194 (1979) · Zbl 0409.90079
[17] Lovász, L., Combinatorial Problems and Exercises (1979), North-Holland: North-Holland Amsterdam · Zbl 0439.05001
[18] Lubiw, A., Λ-free matrices, (Masters thesis (October 1982), University of Waterloo: University of Waterloo Waterloo, Ont)
[19] Natarajan, K. S.; White, L. J., Optimum domination in weighted trees, Inform. Process. Letters, 7, 261-265 (1978) · Zbl 0391.05046
[20] Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32, 597-609 (1970) · Zbl 0216.02602
[21] Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266-283 (1976) · Zbl 0353.65019
[22] Simmons, D. M., Linear Programming for Operations Research (1972), Holden-Day: Holden-Day San Francisco, CA · Zbl 0234.90028
[23] Slater, P. J., \(R\)-domination in graphs, J. Assoc. Comput. Mach., 23, 446-450 (1976) · Zbl 0349.05120
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.