Revised Greedy Algorithm for Partial Domination Problem
Qizhi Fang · Yunchou yu guanli · 2007
In this paper a kind of partial dominating set problems is discussed: given a vertex weighted graph G=(V,E;c) and a positive number K,the objective is to find a subset TV such that at least K vertices of V are dominated by T and the total vertex weight of T is minimized.First,the partial dominating set problem is shown to be NP-hard.Then a revised Greedy algorithm is proposed,which is proved to have the performance ratio H(K).