摘要
支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为lnn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。
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 analyse 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.
出处
《计算机工程与科学》
CSCD
2008年第12期97-101,共5页
Computer Engineering & Science
基金
国家自然科学基金资助项目(60496321)
关键词
支配集
集合击中
近似比
近似算法
dominating set
set hit
approximate ratio
approximation algorithm
