Research of Approximation Algorithm of Vertex Cover

doi:10.16182/j.issn1004731x.joss.201611020

Abstract

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

CLC Number:

TP301.6

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

References 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.