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

• 作者: 幸冬梅
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 支配集 集合击中 近似比 近似算法
• 年，卷（期）: 2008,（12）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 97-101
• 页数: 5页
• 分类号: TP301.6
• 字数: 6777字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2008.12.026

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	幸冬梅	复旦大学计算机科学与工程系	11	6	2.0	2.0