TY  - JOUR
T1  - A Novel Methodology to Measure the Approximation of Near Optimal Algorithms for
Minimum Vertex Cover Problem
AU - Ullah, Zahid AU - Hyun Lee, Su- 
JO  - Journal of Engineering and Applied Sciences
VL  - 15
IS  - 19
SP  - 3391
EP  - 3398
PY  - 2020
DA  - 2001/08/19
SN  - 1816-949x
DO  - jeasci.2020.3391.3398
UR  - https://makhillpublications.co/view-article.php?doi=jeasci.2020.3391.3398
KW  - Graph instances
KW  -minimum vertex cover
KW  -optimization problem
KW  -NP-complete problem
KW  -Maximum Independent Set (MIS)
KW  -approximation algorithm
AB  - 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.
ER  -