一类弱支配集问题的近似算法

摘要：

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

关键词： 支配集 近似比 近似算法 集合覆盖

作者: 幸冬梅

作者单位: 复旦大学计算机科学与工程系,上海,200433;南昌大学数学系,江西,南昌,330047

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 97-101

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）