Research of Approximation Algorithm of Vertex Cover

Authors

Wenyu Gao, School of information science, Guangdong University of Finance and Economics, Guangzhou 510320, China;
Li Hua, School of information science, Guangdong University of Finance and Economics, Guangzhou 510320, China;

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.

Recommended Citation

Gao, Wenyu and Hua, Li (2020) "Research of Approximation Algorithm of Vertex Cover," Journal of System Simulation: Vol. 28: Iss. 11, Article 20.
DOI: 10.16182/j.issn1004731x.joss.201611020
Available at: https://dc-china-simulation.researchcommons.org/journal/vol28/iss11/20

First Page

2784

Revised Date

2015-11-28

DOI Link

https://doi.org/10.16182/j.issn1004731x.joss.201611020

Last Page

2789

CLC

TP301.6

Recommended Citation

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

DOI

10.16182/j.issn1004731x.joss.201611020