The Primal-Dual Algorithms for the Dominating Set and Partial Dominating Set Problems
Qizhi Fang · Computer Engineering and Science · 2008
The dominating set and partial dominating set problems are important combinatorial optimization problems in many applications.Based on their integer program models and the primal-dual method,two approximation algorithms are proposed,both of which have the performance ratio Δ+1(Δ is the maximum vertex degree of the graph concerned).