Comparative Evaluation of Minimum Degree Based Approximation Algorithms for Minimum Vertex Cover Problem
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science and Information Technology
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.