Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(349.52KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
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
1 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.
2 T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. The MIT Press, pp. 1022-1024, 2001.
3 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.
4 B. Monien and E. Speckenmeyer. “Ramsey numbers and an approximation algorithm for the vertex cover problem”. Acta Informatica, vol. 22, pp. 115-123, 1985.
5 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.
6 G. Karakostas. “A better approximation ratio for the vertex cover problem”. ICALP, pp.1043-1050, 2005.
7 G. Rudolph. “Finite Markov chain results in evolutionary computation”. A tour d’horizon,Fundamenta Informaticae, vol. 35, pp. 67-89, 1998.
8 P. Oliveto, J. He, X. Yao. “Evolutionary algorithms and the Vertex Cover problem”. CEC,pp. 1430-1438, 2007.
9 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.
10 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.
11 E. Asgeirsson and C. Stein. “Vertex Cover Approximation on Random Graphs”. WEA 2007, LNCS 4525, pp. 285–296, 2007.
12 I. Dinur and S. Safra. “The importance of being biased”. STOC’02, pp. 33-42, 2002.
13 NWB Team. Network Workbench Tool. Indiana University, North Eastern University, and University of Michigan, http://nwb.slis.indiana.edu/, 2006.
14 S. Gajurel, R. Bielefeld. “A Simple NOVCA: Near Optimal Vertex Cover Algorithm”.Procedia Computer Science, vol. 9, pp 747-753, 2012.
15 K. Xu. “Vertex Cover Benchmark Instances (DIMACS and BHOSLIB)”.http://www.cs.hbg.psu.edu/benchmarks/vertex_cover.html, 2012.
16 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.
17 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.
18 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