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

作     者：高文宇 李华 Gao Wenyu;Li Hua

作者机构：广东财经大学信息学院广州510320 

基　　金：广东省教育厅科技创新项目(2013KJCX0-084) 广东省自然科学基金(8151032001000013) 

出 版 物：《系统仿真学报》 (Journal of System Simulation)

年 卷 期：2016年第28卷第11期

页      码：2784-2789页

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

主 题 词：点覆盖 NP完全 近似算法 参数算法 NT定理 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.16182/j.issn1004731x.joss.201611020

馆 藏 号：203210104...