Implementation and Comparison of Vertex Cover Problem using Various Techniques
|
10.5120/ijca2016910453 |
Reshu Tyagi and Muskaan Batra. Implementation and Comparison of Vertex Cover Problem using Various Techniques. International Journal of Computer Applications 144(10):26-31, June 2016. BibTeX
@article{10.5120/ijca2016910453,
author = {Reshu Tyagi and Muskaan Batra},
title = {Implementation and Comparison of Vertex Cover Problem using Various Techniques},
journal = {International Journal of Computer Applications},
issue_date = {June 2016},
volume = {144},
number = {10},
month = {Jun},
year = {2016},
issn = {0975-8887},
pages = {26-31},
numpages = {6},
url = {http://www.ijcaonline.org/archives/volume144/number10/25216-2016910453},
doi = {10.5120/ijca2016910453},
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
Abstract
The problem of finding Minimum Vertex Cover for graph belongs to the class of NP Complete and plays a key role in Computer Science Theory. The problems which belong to NP Complete set are not solvable in polynomial time in any known way. Since finding Minimum Vertex Cover (MVC) for a graph belongs to NP Complete class; so we are dubious to solve it in any polynomial time algorithm. Such problems are solved by algorithms which promise to give near optimum solution.
In this paper we have analyzed and scrutinized such algorithms like greedy algorithm, approximation algorithm, simple genetic algorithm (GA), primal-dual based algorithm (PDB), Alom’s algorithm etc. on random directed and undirected graphs and found that all the algorithms give near optimum solution with a negligible performance difference. It was also observed that out of all the above said algorithms Alom’s Algorithm is more effective in finding MVC for undirected graphs and for weighted graphs, superior performance is attained by primal-dual based approach.
Further the algorithm was implemented using JAVA and output demonstrates the various possible combinations of Minimum Vertex Cover.
References
- http://cse.unl.edu/~choueiry/Documents/intro_to_npc.pdf
- https://en.wikipedia.org/wiki/Vertex_cover
- Richard M. Karp “Reducibility among Combinatorial Problems” http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
- http://www.gdeepak.com/thesisme/thesisChoosing%20the%20Efficient%20Algorithm%20for%20Vertex%20Cover%20problem.pdf
- Delbot and C. Laforest “A Better list heuristic for vertex Cover” Inf. Process. Lett. 107, 125–127 (2008)
- Eric Angel , Romain Campigotto and Christian Laforest “Algorithm for the vertex cover problem on large graphs.” IBISC Research report (2010)
- Kartik Shah, Praveenkumar Reddy and R. Selvakumar Vertex Cover Problem- Revised Approximation Algorithm
- Jiong Guo, Rolf Niedermeier et al. “Parameterized Complexity of Vertex Cover Variants” Institut f¨ur Informatik, Friedrich-Schiller-Universit¨at Jena,
- Harsh Bhasin, Mohammed Amini “The Applicability of Genetic Algorithm to Vertex Cover” International Journal of Computer Applications(0975-8887) Volume 123 No. 17, August 2015
- Omar Kettani, Faycal Ramdani, Benaissa Tadili “A Heuristic Approach for the vertex Cover Problem” IJCA(0975-8887)Volume 82, No.4-2013
- Imran Khan, Sangeen Khan “Experimental Comparison of Five Approximation Algorithms for minimum Vertex Cover” International Journal of u- and e- Service, Science and Technology Vol. 7, No. 6 (2014), pp. 69-84
- Sushil Chandra Dimri, Kamlesh Chandra Purohit, Durgesh Pant “A greedy approach based Algorithm for the Vertex Cover Problem” International Journal of Scientific and Engineering Research Volume-4, Issue-3, March 2013
- Mohammed Eshtey et al. “NMVSA greedy solution for Vertex Cover Problem” IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 7, No. 3, 2016
- Soumya Godi et al. “Several Algorithms to solve vertex Cover Problem” IJCMS, Vol.4, Issue 4, April 2015
Keywords
Vertex Cover, Approximation, Branch and Bound, Greedy, Alom’s, Primal Dual, Genetic.