Approximation Algorithms For The Positive Influence Dominating Set Problems In Graphs

The dominating set problem in graphs is a classical NP-hard problem in combinatorial optimization.It has important applications in communications,computer networks,wireless transmission sensors.The k-regular graph is a graph in which the degree of each vertex is k.This paper studies two variations of the dominating set problem in the k-regular graph:the connected positive influence dominating set problem and minimum weighted positive influence dominating set problem.For the connected positive influence dominating set problem in the k-regular graph,we first construct a potential function g(·),and discuss its related properties.Secondly,we design a greedy algorithm based on the potential function g(·)to solve the connected positive influence dominating set in the k-regular graph,and prove that the approximate ratio of the greedy algorithm is 2+ln(k~2+2k).For the minimum weighted positive influence dominating set problem in the k-regular graph,we transform the minimum weighted positive influence dominating set problem into the minimum submodular cover problem by constructing a normalized monotone increasing submodular potential function.Therefore,a greedy algorithm is designed to solve the minimum weighted positive influence dominating set in the k-regular graph,and it is proved that the approximate ratio of the greedy algorithm is H(?),where?=k+[?k],? is a real number and 0<?<1.