关键词: 支配集 集合击中 近似比 近似算法

Abstract:

The dominating set problem and the set covering problem are both classic problems in the graph theory. The approximation algorithms for set covering have an important application in many other problems, e.g. in the facility location problem and the server location problem, etc. In this paper, we analy se the relations between the dominating set problem and the set covering problem. We achieve a logn-approximation ratio for the complete dominating set   problem and discuss the minimum size for the weak complete dominating set problem and the weak set b-covering problem. We also analyse their complexities, and achieve nonapproximation for the complete dominating set problem and the weak dominating set problem, etc.

Key words: dominating set, set hit, approximate ratio, approximation algorithm