Please use this identifier to cite or link to this item:
Title: Improved approximation algorithm for vertex cover problem using articulation points
Authors: Patel, S.
Sowmya, Kamath S.
Issue Date: 2014
Citation: 5th International Conference on Computing Communication and Networking Technologies, ICCCNT 2014, 2014, Vol.2014-January, , pp.-
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.
Appears in Collections:2. Conference Papers

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.