Extensions of the Minimum Dominating Set Problem
Nancy V. Phillips · Journal of Information and Optimization Sciences · 1983
The minimun dominating set (MDS] problem is to locate a minimum number of facilities at nodes or a graph so that every other node is connected by an edge to at least one facility. For a general graph, the MDS problem is equivalent to the set covering problem and is NP-complete; however, for a tree graph, polynomial time algorithms exist. This paper presents some results that extend the minimum dominating set problem in an effort to lead to new solution procedures. First, it is shown that every connected graph has a spanning tree such that a MDS for the tree is also a MDS for the graph. Second, the “dual” of the set covering problem, called the star-packing problem, is proved to have the property that a star packing is maximum if and only if the graph contains no augmenting packing.