1. An approximation algorithm for vertex cover problem
Authors : Nishant Jain, Shipra Shukla
Pages : 240-246
DOI : http://dx.doi.org/10.21172/1.71.034
Keywords : minimum vertex cover approximation algorithmgraph breakinggraph rejoing Abstract :The Vertex Cover problem fascinates computer scientists and surfaces in various real world applications. This problem has been proved NP complete in recent future. Therefore one needs to look for polynomial time approximation algorithms to solve the problem. Many algorithms have been developed yet which can find an approximate answer to the problem. We have designed an approximation algorithm to solve vertex cover problem. This algorithm is tested on a large number of graphs adopted from literature [1]. Proposed approximation algorithm yields better covers than 2- approximation algorithm. Proposed algorithm offers superior running time than brute force strategy.
Citing this Journal Article :Nishant Jain, Shipra Shukla, "An approximation algorithm for vertex cover problem", Volume 7 Issue 1 - May 2016, 240-246
Click here to Submit Copyright Takedown Notice for this article.