Improved approximation algorithm for vertex cover problem using articulation points

Abstract

There has been many vertex cover algorithms proposed for the solution of well-known NP-complete class problem of vertex cover. The Vertex Cover problem is important to address in graphs as it has various real world applications viz. Wireless Communication Network, Airline Communication Network, Terrorist Communication Network etc. In this paper, we propose a new algorithm based on Articulation Point, which reduces the vertex cover computation problem in polynomial time and yield solution nearer to an optimal solution, better than the classical approach. We also present a Graphical Visualization Tool that allows the automatic application of the Improved Articulation Point based Approximation Algorithm to process large graphs and finds their articulation points for minimal vertex cover computation. The tool is currently under development.