DocumentCode
3580566
Title
An Improved Greedy Heuristic for Unweighted Minimum Vertex Cover
Author
Tomar, Dhananjay
Author_Institution
Dept. of Comput. Sci. & Eng., Jaypee Inst. of Inf. Technol., Noida, India
fYear
2014
Firstpage
618
Lastpage
622
Abstract
The minimum vertex cover (MVC) problem is a well-studied NP-Complete problem and has various applications. In this paper, a new heuristic approach has been proposed to find the minimum vertex cover of a graph. The proposed algorithm has been tested on random graphs and BHOSLIB instances. The results have shown that the proposed algorithm can yield better solutions especially on dense graphs for solving the minimum vertex cover problem.
Keywords
graph theory; greedy algorithms; heuristic programming; optimisation; random processes; BHOSLIB instances; MVC problem; NP-complete problem; dense graphs; greedy heuristic; random graphs; unweighted minimum vertex cover problem; Algorithm design and analysis; Approximation algorithms; Approximation methods; Benchmark testing; Greedy algorithms; Optimization; Time complexity; NP-hard problem; greedy; heuristic; vertex cover;
fLanguage
English
Publisher
ieee
Conference_Titel
Computational Intelligence and Communication Networks (CICN), 2014 International Conference on
Print_ISBN
978-1-4799-6928-9
Type
conf
DOI
10.1109/CICN.2014.138
Filename
7065558
Link To Document