This paper is aimed to present the solution to vertex cover problem by means of an approximation solution. As it is NP complete problem, we can have an approximate time algorithm to solve the vertex cover problem. We will modify the algorithm to have an algorithm which can be solved in polynomial time and which will give near to optimum solution. It is a simple algorithm which will be based on articulation point. Articulation point can be found using the Depth First Search algorithm. © Springer India 2015.

Praveen Kumar Reddy Maddikunta

Department of Information Technology

School of Information Technology and Engineering

Vellore Campus

Selvakumar R

Department of Mathematics

School of Advanced Sciences

Shah K

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Vertex Cover Problem—Revised Approximation Algorithm

Advances in Intelligent Systems and Computing Artificial Intelligence and Evolutionary Algorithms in Engineering Systems

The minimum vertex cover problem (MVCP) is a well-known NP complete combinatorial optimization problem. The aim of this paper is to present an approximation algorithm for minimum vertex cover problem (MVCP). The algorithm construction is based on articulation points/cut vertices and leaf vertices/pendant vertices. The proposed algorithm assures the near optimal or optimal solution for a given graph and can be solved in polynomial time. A numerical example is illustrated to describe the proposed algorithm. Comparative results show that the proposed algorithm is very competitive compared with other existing algorithms.

Trends in Mathematics Advances in Algebra and Analysis

An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem

Experimental Algorithms Lecture Notes in Computer Science

Implementation and Comparison of Heuristics for the Vertex Cover Problem on Huge Graphs

Automata, Languages and Programming Lecture Notes in Computer Science

Vertex Cover in Graphs with Locally Few Colors

2009 IEEE International Conference on Network Infrastructure and Digital Content

An approximation algorithm for weak vertex cover problem in IP network traffic measurement

Information Processing Letters

A better list heuristic for vertex cover

2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence)

Analysis of population-based evolutionary algorithms for the vertex cover problem

Journal	Data powered by TypesetAdvances in Intelligent Systems and Computing Artificial Intelligence and Evolutionary Algorithms in Engineering Systems
Publisher	Data powered by TypesetSpringer India
ISSN	2194-5357
Open Access	0