A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
Authors:
- D. G. CorneilDCD. G. Corneil
- J. M. KeilJKJ. M. Keil
- 1 October 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 8 (4) , 535-543
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- Decomposing a Polygon into Simpler ComponentsSIAM Journal on Computing, 1985
- A linear algorithm for the domination number of a series-parallel graphDiscrete Applied Mathematics, 1983
- Isomorphism Testing in Hookup ClassesSIAM Journal on Algebraic Discrete Methods, 1982
- Dominating Sets in Chordal GraphsSIAM Journal on Computing, 1982
- Algorithmic Aspects of Vertex Elimination on GraphsSIAM Journal on Computing, 1976
- A linear algorithm for the domination number of a treeInformation Processing Letters, 1975
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972
- The concept of “state” in discrete dynamic programmingJournal of Mathematical Analysis and Applications, 1970