zbMATH — the first resource for mathematics

A dynamic programming approach to the dominating set problem on k-trees. (English) Zbl 0635.05040
Summary: Dynamic programming has long been established as an important technique for demonstrating the existence of polynomial time algorithms for various discrete optimization problems. In this paper we extend the normal paradigm of dynamic programming to allow a polynomial number of optimal solutions to be computed for each subproblem. This technique yields a polynomial time algorithm for the dominating set problem on k-trees, where k is fixed. It is also shown that the dominating set problem is NP- complete for k-trees where k is arbitrary.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory
PDF BibTeX Cite
Full Text: DOI
[1] Booth, KelloggS.; Johnson, J. Howard, Dominating sets in chordal graphs, SIAM J. Comput., 11, 191, (1982) · Zbl 0485.05055
[2] Cockayne, E.; Goodman, S.; Hedetniemi, S., A linear algorithm for the domination number of a tree, Inform. Process. Lett., 4, 41, (1975) · Zbl 0311.68024
[3] Elmaghraby, SalahE., The concept of “state” in discrete dynamic programming, J. Math. Anal. Appl., 29, 523, (1970) · Zbl 0191.49201
[4] Ph.D. ThesisApplication of linear programming duality to problems involving independence and dominationRutgers Univ.New Brunswick, NJavailable as TR81-13, Simon Fraser University, Burnaby, British Columbia, Canada
[5] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039
[6] Gavril, Fănică, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180, (1972) · Zbl 0227.05116
[7] Golumbic, MartinCharles, Algorithmic graph theory and perfect graphs, (1980) · Zbl 0541.05054
[8] Keil, J. Mark, Decomposing a polygon into simpler components, SIAM J. Comput., 14, 799, (1985) · Zbl 0575.68077
[9] Kikuno, Tohru; Yoshida, Noriyoshi; Kakuda, Yoshiaki, A linear algorithm for the domination number of a series-parallel graph, Discrete Appl. Math., 5, 299, (1983) · Zbl 0507.05060
[10] Klawe, M. M.; Corneil, D. G.; Proskurowski, A., Isomorphism testing in hookup classes, SIAM J. Algebraic Discrete Methods, 3, 260, (1982) · Zbl 0503.05023
[11] Rose, DonaldJ.; Tarjan, R. Endre; Lueker, GeorgeS., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266, (1976) · Zbl 0353.65019
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.