Call for Paper - October 2019 Edition
IJCA solicits original research papers for the October 2019 Edition. Last date of manuscript submission is September 20, 2019. Read More

A GA based Approach to Find Minimal Vertex Cover

Print
PDF
IJCA Proceedings on National Conference cum Workshop on Bioinformatics and Computational Biology
© 2014 by IJCA Journal
NCWBCB - Number 3
Year of Publication: 2014
Authors:
Udit Kr. Chakraborty
Debanjan Konar
Chandralika Chakraborty

Udit Kr. Chakraborty, Debanjan Konar and Chandralika Chakraborty. Article: A GA based Approach to Find Minimal Vertex Cover. IJCA Proceedings on National Conference cum Workshop on Bioinformatics and Computational Biology NCWBCB(3):5-7, May 2014. Full text available. BibTeX

@article{key:article,
	author = {Udit Kr. Chakraborty and Debanjan Konar and Chandralika Chakraborty},
	title = {Article: A GA based Approach to Find Minimal Vertex Cover},
	journal = {IJCA Proceedings on National Conference cum Workshop on Bioinformatics and Computational Biology},
	year = {2014},
	volume = {NCWBCB},
	number = {3},
	pages = {5-7},
	month = {May},
	note = {Full text available}
}

Abstract

Genetic Algorithms are a class of Optimization Techniques which has been developed under inspiration of the Darwinian Theory of Survival of the Fittest. This technique has been successfully used to solve many optimization problems which otherwise pose huge challenges for computation. This paper presents a GA based approach to solve the Minimal Vertex Cover problem of Graph Theory.

References

  • Samir Roy, Udit Chakraborty, Introduction to Soft Computing – Neuro-Fuzzy and Genetic Algorithms, Pearson Education, 2013.
  • J. -M. Renders, H. Bersini, "Hybridizing genetic algorithms with hill-climbing methods for global optimization: two possible ways", Proceedings of the First IEEE Conference on Evolutionary Computation, vol. 1 (1994), 312,317.
  • I. Dinur and S. Safra, "On the hardness of approximating minimum vertex cover", Annals of Mathematics, 162 (2005), 439–485.
  • C. Papadimitriou and M. Yannakakis, "Optimization, approximation and complexity classes", Journal of Computer and System Sciences 43 (1991), 424–440.
  • P. S. Oliveto, J. He and X. Yao, "Evolutionary Algorithms and the Vertex Cover Problem", IEEE Congress on Evolutionary Computation (2007), 1870-1877.
  • S. Khuri and T. Black, "An evolutionary heuristic for the minimum vertex cover problem", in Genetic Algorithms within the Framework of Evolutionary Computation- Proceedings of the KI-94 Workshop, J. Hopf, Ed. , Saarbrucken, Germany, 1994, pp. 86-90Forman, G. 2003. An extensive empirical study of feature selection metrics for text classification. J. Mach. Learn. Res. 3 (Mar. 2003), 1289-1305.
  • K. S. Christos. H. Papadimitriou, CombinatorialOptimization: Algorithms and Complexity, Dover Publications Inc. , 1982.