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

摘要：

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

关键词：点覆盖、NP完全、近似算法、参数算法、NT定理

所属期刊栏目：28

分类号：TP301.6(计算技术、计算机技术)

资助基金：广东省教育厅科技创新项目2013KJCX0084,广东省自然科学基金8151032001000013;

在线出版日期：2016-12-12（万方平台首次上网日期，不代表论文的发表时间）

页码：2784-2789