Modified Vertex Support Algorithm: A New approach for approximation of Minimum vertex cover
Imran Khan, Khan Hasham · 2013
Graph related problems mostly belong to NP class and minimum vertex cover is one of them. Minimum vertex cover is focus point for researchers since last decade due to its vast areas of application. In this research paper we have presented a modified form of approximation algorithm for minimum vertex cover which makes use of data structure proposed already named vertex support. We changed the way of selection slightly from vertex support algorithm, vertices attached to minimum support node play very critical role in selection of vertices for minimum vertex cover and we used this in our algorithm. Using our approach we managed to reduce worst case approximation ratio of VSA which is 1.583 to 1.064, this is very major change in providing results with simplicity. Results are also compared with MDG and NOVAC in order to demonstrate the efficiency of selecting vertices in this manner. Simplicity in design can help in applying it in time restricted environments.