@article{MAKHILLJEAS2020151919452,
    title = {A Novel Methodology to Measure the Approximation of Near Optimal Algorithms for
Minimum Vertex Cover Problem},
    journal = {Journal of Engineering and Applied Sciences},
    volume = {15},
    number = {19},
    pages = {3391-3398},
    year = {2020},
    issn = {1816-949x},
    doi = {jeasci.2020.3391.3398},
    url = {https://makhillpublications.co/view-article.php?issn=1816-949x&doi=jeasci.2020.3391.3398},
    author = {Zahid and},
    keywords = {Graph instances,minimum vertex cover,optimization problem,NP-complete problem,Maximum Independent Set (MIS),approximation algorithm},
    abstract = {Many algorithms have been proposed for the
solution of the Minimum Vertex Cover (MVC) problem
but the researchers are unable to find the optimality of an
approximation algorithm. In this study, we have proposed
a method to evaluate that either the result returned by an
approximation algorithm for the minimum vertex cover
problem is optimal or not. The proposed method is tested
on three algorithms, i.e., Maximum Degree Greedy
(MDG) algorithm, Modified Vertex Support Algorithm
(MVSA) and Clever Steady Strategy Algorithm (CSSA).
The proposed method provides an opportunity to test the
optimality of an approximation algorithm for MVC
problem with low computation complexity. The proposed
method has performed well during experimentation and its
results brighten the path of successful implementation of
the method for the evaluation of approximation algorithms
for the Minimum Vertex Cover (MVC) problem. The
testing of the proposed method was carried out on small
graph instances. The proposed method has resolved the
problem to test the optimality of the approximation
algorithm for the minimum vertex cover problem. This
technique has digitized the process of finding out the
accuracy of the optimal solution returned by
approximation algorithms for MVC.}
    }