Analysis of Various Algorithms to Solve Vertex Cover Problem
Sangeeta Bansal1, Ajay Rana2
1Sangeeta Bansal, Student M.Tech, Department of Computer Science, Amity University, Noida (U.P), India.
2Dr. Ajay Rana, Director, Department of Computer Science, Amity University, Noida (U.P), India
Manuscript received on 10 May 2014 | Revised Manuscript received on 20 May 2014 | Manuscript Published on 30 May 2014 | PP: 4-6 | Volume-3 Issue-12, May 2014 | Retrieval Number: L16290531214/14©BEIESP
Open Access | Editorial and Publishing Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: The vertex cover (VC) problem belongs to the class of Non Deterministic Polynomial time complete (NPC) graph theoretical problems, which plays a central role in theoretical computer science and it has a numerous real life applications. Since the problem is Non Deterministic Polynomial time complete (NPC) it is unlikely to find a polynomial-time algorithm for solving vertex-cover problem exactly. This paper analyses the various algorithms to find minimum vertex cover for standard classes of random graph. The performance of all algorithms is compared with the complexity and the output solution that of the approximation algorithm, clever greedy algorithm, branch-and-bound algorithm, and simple genetic algorithm (GA).
Keywords: Minimum Vertex Cover, Branch And Bound, Greedy Algorithm, Genetic Algorithm, Crossover, Mutation.
Scope of the Article: Web Algorithms