A New Approximation Algorithm for Vertex Cover Problem

Vertex Cover Problem is one among NP-Complete problems. So neither the proof of existence of a optimal solution algorithm nor the proof of no existence of such solution has been given yet. So it is desirable to try to find a near optimal solution. In this paper we give a brief introduction of existing algorithms and propose a new heuristic algorithm. This new algorithm has polynomial running time and produces a near optimal solution for the unweighted graphs and outperforms compared to the existing approximation algorithms for graph.