원문정보
초록
영어
Numerous approximation algorithms have been presented by researchers for approximation of minimum vertex cover, all of these approaches have deficiencies in one way or another. As minimum vertex cover is NP-Complete so we can’t find out optimal solution so approximation is the way left but it is very hard for someone to decide which one procedure to use, in this comparison paper we have selected five approximation algorithms and have drawn detailed experimental comparison. Best available benchmarks were used for the comparison process which was to compare multiple algorithms for the same task on different aspects. Extensive results have been provided to clarify the selection process, probability of production optimal solutions, run time complexity and approximation ratio were factors involved in the process of selection.
목차
1. Introduction
2. Literature Review
3. The Algorithms
3.1. Maximum Degree Greedy (MDG)
3.2. Vertex Support Algorithm (VSA)
3.3. Nearly Optimal Vertex Cover (NOVAC-1)
3.4. Advanced Vertex Support Algorithm (AVSA)
3.5. Modified Vertex Support Algorithm (MVSA)
4. Experimental Comparison
4.1. Capability of Producing Optimal Solutions
4.2. Comparison on the Basis of Approximation Ratio
4.2. Comparison on the Basis of Run Time Complexity
5. Conclusion
References