Volume 7 Issue 1 - May 2016

  • 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", https://www.ijltet.org/journal_details.php?id=901&j_id=3050, Volume 7 Issue 1 - May 2016, 240-246, #ijltetorg