CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

The Applicability of Genetic algorithm to Vertex Cover

by Harsh Bhasin, Mohammad Amini
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 123 - Number 17
Year of Publication: 2015
Authors: Harsh Bhasin, Mohammad Amini
10.5120/ijca2015905785

Harsh Bhasin, Mohammad Amini . The Applicability of Genetic algorithm to Vertex Cover. International Journal of Computer Applications. 123, 17 ( August 2015), 29-34. DOI=10.5120/ijca2015905785

@article{ 10.5120/ijca2015905785,
author = { Harsh Bhasin, Mohammad Amini },
title = { The Applicability of Genetic algorithm to Vertex Cover },
journal = { International Journal of Computer Applications },
issue_date = { August 2015 },
volume = { 123 },
number = { 17 },
month = { August },
year = { 2015 },
issn = { 0975-8887 },
pages = { 29-34 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume123/number17/22054-2015905785/ },
doi = { 10.5120/ijca2015905785 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:12:59.483487+05:30
%A Harsh Bhasin
%A Mohammad Amini
%T The Applicability of Genetic algorithm to Vertex Cover
%J International Journal of Computer Applications
%@ 0975-8887
%V 123
%N 17
%P 29-34
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Vertex Cover Problem calls for the selection of a set of vertices(V) in a way that all the edges of the graph, connected to those vertices constitute the set E of the given graph G= (V, E). The problem finds applications in various fields and is therefore, one of the most widely researched topics in NP Complete Problems. The problem is an NP Complete problem this work proposes a Genetic Algorithm based solution to handle the problem. The proposed algorithm has been implemented and tested for various graphs. These instances vary in the number of vertices and connectivity. The results are encouraging. This paper also explores the available techniques in order to put the things in the perspective. The future scope of this work intends to apply Diploid Genetic Algorithms to the problem to incorporate robustness into the proposed algorithm.

References
  1. Bhasin, H. et Al., 2012, Harnessing Genetic Algorithm for Vertex Cover Problem, International Journal on Computer Science and Engineering (IJCSE), ISSN : 0975-3397, Vol. 4 No. 02.
  2. Corman H. Thomas, Leiserson E. Charles, Rivest L. Ronald, Stein Clifford “Introduction to Algorithms” Second Edition McGrawHill Book Compan(EP98).
  3. Evans, I.K.  (1998)  Evolutionary algorithms for vertex Cover, ©1998. To appear in Evolutionary Programming VII, Proceedings Seventh International Conference (EP98).
  4. Friedrich, T., et Al,(2008) Analyses of Simple Hybrid Algorithms for the Vertex Cover Problem, by the Massachusetts Institute of Technology, Evolutionary Computation
  5. Oliveto, P.S., He, J. and Yao, X.  (2007)  Evolutionary algorithms and the vertex cover problem 1-4244-1340-0/07/ IEEE
  6. S.J, et Al.(2004) An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem, Annals of Operations Research 131, 283–304.
  7. Wu, F., Li, K., Sallam, A. and Zhou, X.  (2013)  A molecular solution for minimum vertex cover problem in tile assembly model, Published online: 16 March 2013 © Springer Science+Business Media New York 2013, J Supercomput (2013) 66:148–169 DOI 10.1007/s11227-013-0892-0
  8. Voß, S. and Fink, A. , (2012) , A hybridized tabu search approach for the minimum weight vertex cover problem, J Heuristics 18:869–876 DOI 10.1007/s10732-012-9211-9
  9. Zhou, T., Lu, Z., Wang, Y., Ding, J. and Peng, B.  (2015)  Multi-start iterated tabu search for the minimum weight vertex cover problem,    Springer Science+Business Media New York 2015, J Comb Optim DOI 10.1007/s10878-015-9909-3
  10. S. Balaji, , (2013) A New Effective Local Search Heuristic for the Maximum clique problem , World Academy of Science, Engineering and Technology International Journal of Mathematical, Computational, Statistical, Natural and Physical Engineering Vol:7, No:5.
  11. Pullan, W.,(2007) Approximating the maximum vertex/edge weighted clique using local search, Published online: 4 May 2007 Springer Science+Business Media.
  12. Kratsch, K. and Neumann, F.  (2012)  Fixed-parameter evolutionary algorithms and the vertex cover problem Springerlink.com, Algorithmica (2013) 65:754–771 DOI 10.1007/s00453-012-9660-4
  13. Milanovic, M. (2010) Solving the generalized vertex cover problem by genetic algorithm, Computing and Informatics, Vol. 29, 1251–1265
  14. Bhasin, H., On the applicability of Diploid Genetic Algorithms in Dynamic Environments,(2014), IEEE,  2014 Intl. Conference on Soft Computing and Machine Intelligence
  15. Safar, M. and Habib, S. (2007) Hard constrained vertex cover communication algorithm for WSN , T.-W. Kuo et al. (Eds.): EUC 2007, LNCS 4808, pp. 635–649, IFIP International Federation for Information Processing
  16. Singh, A. and Gupta, A.K. (2006) A hybrid heuristic for the maximum clique problem, Springer Science + Business Media,, J Heuristics (2006) 12: 5–22 DOI 10.1007/s10732-006-3750-x
  17. Khuri, S. and Back, T. (1994) An evolutionary heuristic for the minimum vertex cover problem http://www.researchgate.net/publication/2581134
  18. Chandu, D.P. (20014) A parallel genetic algorithm for generalized vertex cover problem (IJCSIT) International Journal of Computer Science and Information Technologies, Vol. 5 (6) , 7686-7689
  19. Karp, R.M., (1972). "Reducibility Among Combinatorial Problems" (PDF). In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103.
  20. Bhasin, H. et. al, On the Applicability of Diploid Genetic Algorithms, AI and Society, Springer (In Press).
  21. Bhasin, H. et. al., On The Applicability of Diploid Genetic Algorithms in Dynamic Environments, Soft Computing, Springer. DOI: 10.1007/s00500-015-1803-5.
  22. Bhasin, H., et. al., On the Applicability of Diploid Genetic Algorithms, AI and Society, Springer, DOI: 10.1007/s00146-015-0591.
Index Terms

Computer Science
Information Sciences

Keywords

Keywords are Vertex Cover Problem NP Completeness Genetic Algorithm Artificial Intelligence.

Powered by PhDFocusTM