Home   >   CSC-OpenAccess Library   >    Manuscript Information
A Fast Near Optimal Vertex Cover Algorithm (NOVCA)
Sanjaya Gajurel, Roger Bielefeld
Pages - 9 - 18     |    Revised - 15-09-2012     |    Published - 25-10-2012
Volume - 3   Issue - 1    |    Publication Date - October 2012  Table of Contents
MORE INFORMATION
KEYWORDS
Vertex Cover Problem, Combinatorial Problem, NP-Complete Problem, Approximation Algorithm
ABSTRACT
This paper describes an extremely fast polynomial time algorithm, the Near Optimal Vertex Cover Algorithm (NOVCA) that produces an optimal or near optimal vertex cover for any known undirected graph G (V, E). NOVCA is based on the idea of (i) including the vertex having maximum degree in the vertex cover and (ii) rendering the degree of a vertex to zero by including all its adjacent vertices. The two versions of algorithm, NOVCA-I and NOVCA-II, 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 other available vertex cover algorithms.
CITED BY (4)  
1 Eshtay, M., Sliet, A., & Sharieh, A. NMVSA Greedy Solution for Vertex Cover Problem. vertex, 2, 15.
2 Gajurel, S., Cleveland, U. S., & Bielefeld, R. (2015, September). Mutated Near Optimal Vertex Cover Algorithm (NOVCA) Visualization on a Tile Display. In Cluster Computing (CLUSTER), 2015 IEEE International Conference on (pp. 525-526). IEEE.
3 Gajurel, S., & Bielefeld, R. (2014). A Heuristic Approach to Fast NOVCA (Near Optimal Vertex Cover Algorithm). Computer Technology and Application, 5(2).
4 Cai, S., Su, K., Luo, C., & Sattar, A. (2013). NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 687-716.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
B. Monien and E. Speckenmeyer. “Ramsey numbers and an approximation algorithm for the vertex cover problem”. Acta Informatica, vol. 22, pp. 115-123, 1985.
E. Asgeirsson and C. Stein. “Vertex Cover Approximation on Random Graphs”. WEA 2007, LNCS 4525, pp. 285–296, 2007.
E. Halperin. “Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs”. SIAM J. on Computing, vol. 31, pp. 1608-1623, 2002. Also in Proc. of 11th SODA, pp. 329-337, 2000.
F. Abu-Khazm, M. Fellows, M. Langston, and W. Suters. “Crown Structures for Vertex Cover Kernelization”. Theory Comput. Systems, vol. 41, pp. 411-430, 2007.
G. Karakostas. “A better approximation ratio for the vertex cover problem”. ICALP, pp.1043-1050, 2005.
G. Rudolph. “Finite Markov chain results in evolutionary computation”. A tour d’horizon,Fundamenta Informaticae, vol. 35, pp. 67-89, 1998.
I. Dinur and S. Safra. “The importance of being biased”. STOC’02, pp. 33-42, 2002.
J. Chen, I. Kanj and G. Xia. “Simplicity Is Beauty: Improved Upper Bounds for Vertex Cover”. Technical report TR05-008, School of CTI, DePaul University, 2005.
K. Xu. “Vertex Cover Benchmark Instances (DIMACS and BHOSLIB)”.http://www.cs.hbg.psu.edu/benchmarks/vertex_cover.html, 2012.
NWB Team. Network Workbench Tool. Indiana University, North Eastern University, and University of Michigan, http://nwb.slis.indiana.edu/, 2006.
P. Oliveto, J. He, X. Yao. “Evolutionary algorithms and the Vertex Cover problem”. CEC,pp. 1430-1438, 2007.
R. Bar-Yehuda and S. Even. “A local-ratio theorem for approximating the weighted vertex cover problem”. North-Holland Mathematics Studies, vol. 109, pp. 27-45, 1985.
R. Karp. “Reducibility among combinatorial problems”. In R. E. Miller and J. W. Thatcher(eds.). Complexity of Computer Computations, Plenum Press, NY, pp. 85-103, 1972.
S. Cai, K. Su and A. Sattar. “Local Search with Edge Weighting and Configuration Checking Heuristics for Minimum Vertex Cover”. Artif. Intell., vol. 175 pp. 1672-1696,2011.
S. Gajurel, R. Bielefeld. “A Simple NOVCA: Near Optimal Vertex Cover Algorithm”.Procedia Computer Science, vol. 9, pp 747-753, 2012.
S. Richter, M. Helmert, and C. Gretton. “A Stochastic Local Search Approach to Vertex Cover”. In Proceedings of the 30th German Conference of Artificial Intelligence (KI), pp 412-426, 2007.
T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. The MIT Press, pp. 1022-1024, 2001.
W. Pullan. “Phased Local Search for the Maximum Clique Problem”. J. Comb. Optim.,vol. 12, pp. 303-323, 2006.
Dr. Sanjaya Gajurel
Case Western Reserve University - United States of America
sxg125@case.edu
Dr. Roger Bielefeld
Case Western Reserve University - United States of America


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS