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
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;
Conference_Titel :
Computational Intelligence and Communication Networks (CICN), 2014 International Conference on
Print_ISBN :
978-1-4799-6928-9
DOI :
10.1109/CICN.2014.138
