Open    Access



A Heuristic Approach to Fast NOVCA (Near Optimal Vertex Cover Algorithm)





Author(s)

Sanjaya Gajurel and Roger Bielefeld

Full-Text PDF XML     641 Views

DOI:10.17265/1934-7332/2014.02.004

ITS, Advanced Research ComputingCWRU

This paper describes an extremely fast polynomial time algorithm, the NOVCA （Near Optimal Vertex Cover Algorithm）
that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA is based on the idea of (1) including the vertex having maximum degree in the vertex cover and (2) rendering the degree of a vertex to zero by including all its adjacent vertices. The three versions of algorithm, NOVCA-I, NOVCA-II, and NOVCA-random, have been developed. The results identifying bounds on the size of the minimum vertex cover as well as polynomial complexity of algorithm are given with experimental verification. Future research efforts will be directed at tuning the algorithm and providing proof for better approximation ratio with NOVCA compared to any available vertex cover algorithms.

Vertex cover problem, combinatorial problem, NP-complete problem, approximation algorithm, optimization,
algorithms.