Comparative Evaluation of Minimum Degree Based Approximation Algorithms for Minimum Vertex Cover Problem

Abstract

Minimum vertex cover(MVC) problem is a NP Complete optimization problem that attracts many researchers due to its wide range of application in real life problems. As MVC is NPcomplete,

there are no any algorithm that finds optimal solution to MVC problem in polynomial time. Numerous of approaches have been proposed among which approximation approach is much favored in the field of MVC as it guarantees to give a solution that is near to optimal or sub optimal solution. There is a number of MVC algorithm based on approximation approaches that constructs vertex cover .This Dissertation work is focused on a comparative study of three recent approximation approach based algorithms ,NOVCA,CSSA and NMVSA. The performance of each algorithm is measured in terms of approximation ratio and step count. Here step count is used as second performance metrics because the performance differences in approximation ratio of all the algorithms are relatively small. In the dissertation work, benchmark graph datasets are used for the comparison of algorithms and an extensive analysis have been provided to help the selection of efficient algorithm.