Abstract:
A mixed dominating set for a graph G=(V,E) is a set S⊆V∪E such that every element x∈(V∪E)∖S is either adjacent or incident to an element of S. The mixed domination number of a graph G, denoted by γm(G), is the minimum cardinality of mixed dominating sets of G. Any mixed dominating set with the cardinality of γm(G) is called a minimum mixed dominating set. The mixed domination set (MDS) problem is to find a minimum mixed dominating set for a graph G and is known to be an NP-complete problem. In this paper, we present a novel approach to find all of the mixed dominating sets, called the AMDS problem, of a graph with bounded tree-width tw. Our new technique of assigning power values to edges and vertices, and combining with dynamic programming, leads to a fixed-parameter algorithm of time O(3tw2×tw2×|V|). This shows that MDS is fixed-parameter tractable with respect to tree-width. In addition, we theoretically improve the proposed algorithm to solve the MDS problem in O(6tw×|V|) time.
