Earticle

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.

Approximation methods are best way to deal NP optimization problems and MVC is one of these. In this research paper we have presented a new extra fast approximation algorithm for solving MVC generally in all graphs. The proposed algorithm is named degree contribution algorithm (DCA), a new data structure proposed and employed in this algorithm, name degree contribution. It is first time in literature that such a sophisticated data structure for graphs is proposed which take account of whole graph for each node contribution value. All decisions regarding vertices are made on the basis of the proposed data structure. Effectiveness of DCA is shown by applying it to best available benchmarks and after large number of experiments worst approximation ratio recorded was 1.041 and an average approximation ratio was 1.005. These results show that algorithm can perform well in solving graphs faster as compared to other algorithms present.