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

doi:10.16182/j.issn1004731x.joss.201611020

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (11): 2784-2789.doi: 10.16182/j.issn1004731x.joss.201611020

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

高文宇, 李华

广东财经大学信息学院,广州 510320

收稿日期:2015-03-19 修回日期:2015-11-28 出版日期:2016-11-08 发布日期:2020-08-13
作者简介:高文宇(1972-),男,湖南永州,博士,教授,研究方向为算法理论及应用。
基金资助:
广东省教育厅科技创新项目(2013KJCX0-084),广东省自然科学基金(8151032001000013)

Research of Approximation Algorithm of Vertex Cover

Gao Wenyu, Li Hua

School of information science, Guangdong University of Finance and Economics, Guangzhou 510320, China

Received:2015-03-19 Revised:2015-11-28 Online:2016-11-08 Published:2020-08-13

摘要/Abstract

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

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

Abstract: Vertex cover is one of the most important NP complete problems, and it is also one of the most studied problems in parameterized algorithm design in recent years. According to some deficiencies of existing vertex cover approximation algorithms, a novel NT theorem based 2-approximation algorithm was proposed based on advances in parameterized algorithm. The new algorithm first used kernelization technology to reduce the origin graph, then used greedy strategy to guide the vertex selection in the remaining graph, kernelization provided effective guarantee for the approximation algorithm. In order to test the performance of the new algorithm, simulations on different types of random graph were carried to compare the new algorithm and the classical matching-based 2-approximation algorithm. Simulation results show that the new algorithm outperforms the matching-based 2-approximation algorithm.

Key words: vertex cover, NP complete, approximation algorithm, parameterized algorithm, NT theorem

中图分类号:

TP301.6

高文宇, 李华. 点覆盖问题的近似算法研究[J]. 系统仿真学报, 2016, 28(11): 2784-2789.

Gao Wenyu, Li Hua. Research of Approximation Algorithm of Vertex Cover[J]. Journal of System Simulation, 2016, 28(11): 2784-2789.

参考文献 15

[1]	West D B.Introduction to graph theory[M]. Second edition ed. USA: Prentice Hall, 2001.
[2]	Downey R G, Fellows M R.Parameterized Complexity[M]// Monographs in Computer Science. New York, USA: Springer-Verlag New York Inc., 1999: 548.
[3]	Flum J, Grohe M.Parameterized Complexity Theory[M]// ed. by W Brauer, G Rozenberg, A Salomaa, Texts in Theoretical Computer Science. An EATCS Series Berlin, Germany: SpringerVerlag, 2006: 495.
[4]	Buss J F, Goldsmith J.Nondeterminism within P[J]. Siam J. Comput.(S1064-8275), 1993, 22(3): 560-572.
[5]	Downey R G, Fellows M R.Parameterized Computational Feasibility[M]// Feasible Mathematics II Progress in Computer Science and Applied Logic. USA: Birkhäuser Boston, 1995: 219-244.
[6]	Balasubramanian R, Fellows M R, Raman V.An improved fixed-parameter algorithm for vertex cover[J]. Information Processing Letters (S0020-0190), 1998, 65(3): 163-168.
[7]	Chen J, Kanj I A, Jia W.Vertex Cover: Further Observations and Further Improvements[J]. Journal of Algorithms (S0196-6774), 2001, 41(2): 280-301.
[8]	Chen J, Kanj I A, Xia G.Improved upper bounds for vertex cover[J]. Theoretical Computer Science (S0304-3975), 2010, 411(40/42): 3736-3756.
[9]	李绍华, 王建新, 冯启龙, 等. 参数计算中核心化技术及其应用[J]. 软件学报, 2009, 20(9): 2307-2319.
[10]	Nemhauser G L, Trotter L E.Vertex packing: structural properties and algorithms[J]. Mathematical Programming (S0025-5610), 1975, 8(1): 232-248.
[11]	Bar-yehuda R, Even S. A local-ratio theorem for approxmating the weighted vertex cover problem[J]. North-Holland Mathematics Studies (S0356-2670), 1985, 109(1) : 27-45.
[12]	Dinic E A.Algorithm for solution of a problem of maximum flows in networks with power estimation[J]. Soviet Mathematics Doklady (S1064-5624), 1970, 11(11): : 1277-1280.
[13]	李军侠, 吴卫山. 加权快速聚类距离解模糊算法[J]. 系统仿真学报, 2012, 24(4): 868-872.
[14]	郭晓军, 胡云安, 张雷. 单变量多单元半全局极值搜索算法仿真研究[J]. 系统仿真学报, 2013, 25(8): 1901-1906.
[15]	王强, 张安, 宋志蛟. UAV协同任务分配的改进DPSO算法仿真研究[J]. 系统仿真学报, 2014, 26(5): 1149-1155.

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

Research of Approximation Algorithm of Vertex Cover

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价

[1]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[2]	李建锋, 卢迪, 李贺香. 一种改进的原子搜索算法[J]. 系统仿真学报, 2022, 34(3): 490-502.
[3]	董君, 叶春明. 半导体晶圆节能分布式制造与预维护联合优化[J]. 系统仿真学报, 2022, 34(3): 584-602.
[4]	王付宇, 汤涛. 双种群鱼群算法在分布式投资组合的应用[J]. 系统仿真学报, 2021, 33(9): 2074-2084.
[5]	刘景森, 袁蒙蒙, 李煜. 基于改进樽海鞘群算法求解工程优化设计问题[J]. 系统仿真学报, 2021, 33(4): 854-866.
[6]	顾菊平, 程天宇, 王建平, 华亮, 赵凤申, 蒋凌. 基于几何特征不变量的快速3D医学图像配准[J]. 系统仿真学报, 2020, 32(11): 2105-2111.
[7]	陆湛文, 程新功, 张永峰. 基于共识粒子群的全局优化求解方法[J]. 系统仿真学报, 2020, 32(10): 1936-1942.
[8]	刘长良, 王梓齐. 基于严格二叉树编码和GA的模糊树结构学习[J]. 系统仿真学报, 2020, 32(8): 1473-1480.
[9]	刘景森, 刘晓珍, 李煜. 具有动态步长和发现概率的布谷鸟搜索算法[J]. 系统仿真学报, 2020, 32(2): 289-298.
[10]	顾菊平, 程天宇, 华亮, 王建平, 赵剑, 曹涌. 面向脊柱生物建模的图像分割与配准研究综述[J]. 系统仿真学报, 2019, 31(2): 167-173.
[11]	陆秋琴, 黄光球. 捕食-被食动力学优化算法[J]. 系统仿真学报, 2018, 30(10): 3975-3984.
[12]	李荣雨, 梁栋, 戚桂洪. 基于自适应反馈机制的精英教学优化算法[J]. 系统仿真学报, 2018, 30(8): 2950-2957.
[13]	李琦, 赵峰. 基于气温与日期类型的改进BP网络热负荷预测[J]. 系统仿真学报, 2018, 30(4): 1464-1472.
[14]	刘长良, 王鹏飞, 刘帅, 罗磊, 回振桥. 一种改进的CS算法及其在微电网优化中的应用[J]. 系统仿真学报, 2018, 30(3): 930-936.
[15]	肖辉辉, 段艳明. 具有入侵杂草策略的花朵授粉算法[J]. 系统仿真学报, 2017, 29(2): 264-272.