Constant Time Computation of Minimum Dominating Sets
Marilynn Livingston, Quentin F. Stout · 1994
Let G be a graph and let P (n) denote an element from a one-parameter family of graphs, such as a path of length n, a cycle of length n, or a complete binary tree of height n. We are concerned with determining minimum dominating sets of graphs of the form G \\Theta P (n). Using dynamic programming and properties of finite state spaces, we show a constant time algorithm to produce a minimum dominating set of G \\Theta P (n), for fixed G and all n, for the one-parameter families mentioned. Previous researchers had used similar techniques but obtained only lineartime algorithms. We also show how a closed form expression can be obtained for the minimum domination number of G \\Theta P (n). We discuss extensions of the algorithm to the determination of all minimum dominating sets for G \\Theta P (n), and to related problems of coverings, packings, and codes. In addition, we discuss algorithm extensions to several different types of domination, including perfect domination, and to other ways of ...