论文部分内容阅读
支配集问题和集合覆盖问题均是图论中的经典问题，尤其是集合覆盖问题，它的近似算法在许多其他问题中均有非常多的应用，如设施选址问题、服务器的安置问题等。本文研究了支配集问题和集合覆盖问题的关系，讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等，给出完全支配集问题的近似比为Inn的近似算法，分析了弱完全支配集问题的不可近似比最小规模，讨论了集合击中问题和弱集合b-覆盖问题的最小规模，同时讨论了完全支配集问题、集合d-击中等问题的不可近似性。