点覆盖问题的近似算法研究

• 作者: 李华 高文宇
• 来源期刊: 系统仿真学报
• 学科: 工学
• 关键词: 点覆盖 NP完全 近似算法 参数算法 NT定理
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: 仿真应用工程
• 页码范围: 2784-2789
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.16182/j.issn1004731x.joss.201611020

摘要

点覆盖问题是最重要的NP完全问题之一,也是近年来参数算法设计中研究得最多的问题之一.针对现有点覆盖近似算法的一些不足,基于点覆盖问题参数算法的进展,提出了该问题一个基于NT定理规约的2-近似算法.利用了参数算法中的核化技术对图进行化简,在剩余图上采用贪心策略来指导节点的选择,核化技术为算法提供了有效的近似度保障.为检验新算法性能,在不同类型的随机图上通过仿真实验比较了新算法和经典的基于匹配的2-近似算法.仿真实验结果表明新算法较基于匹配的2-近似算法有着明显的优势.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高文宇	广东财经大学信息学院	2	1	1.0	1.0
2	李华	广东财经大学信息学院	3	2	1.0	1.0