Call for Paper - March 2023 Edition
IJCA solicits original research papers for the March 2023 Edition. Last date of manuscript submission is February 20, 2023. Read More

Implementation and Comparison of Vertex Cover Problem using Various Techniques

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
Reshu Tyagi, Muskaan Batra
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

  1. http://cse.unl.edu/~choueiry/Documents/intro_to_npc.pdf
  2. https://en.wikipedia.org/wiki/Vertex_cover
  3. Richard M. Karp “Reducibility among Combinatorial Problems” http://www.cs.berkeley.edu/~luca/cs172/karp.pdf
  4. http://www.gdeepak.com/thesisme/thesisChoosing%20the%20Efficient%20Algorithm%20for%20Vertex%20Cover%20problem.pdf
  5. Delbot and C. Laforest “A Better list heuristic for vertex Cover” Inf. Process. Lett. 107, 125–127 (2008)
  6. Eric Angel , Romain Campigotto and Christian Laforest “Algorithm for the vertex cover problem on large graphs.” IBISC Research report (2010)
  7. Kartik Shah, Praveenkumar Reddy and R. Selvakumar Vertex Cover Problem- Revised Approximation Algorithm
  8. Jiong Guo, Rolf Niedermeier et al. “Parameterized Complexity of Vertex Cover Variants” Institut f¨ur Informatik, Friedrich-Schiller-Universit¨at Jena,
  9. 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
  10. Omar Kettani, Faycal Ramdani, Benaissa Tadili “A Heuristic Approach for the vertex Cover Problem” IJCA(0975-8887)Volume 82, No.4-2013
  11. 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
  12. 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
  13. 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
  14. 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.