Research Article | Open Access | Download PDF
Volume 3 | Issue 2 | Year 2013 | Article Id. IJCOT-V3I4P10 | DOI : https://doi.org/10.14445/22492593/IJCOT-V3I4P10
Modified Genetic Algorithm for Maximum Clique Problem
Naresh Kumar, Deepkiran Munjal
Citation :
Naresh Kumar, Deepkiran Munjal, "Modified Genetic Algorithm for Maximum Clique Problem," International Journal of Computer & Organization Trends (IJCOT), vol. 3, no. 2, pp. 40-42, 2013. Crossref, https://doi.org/10.14445/22492593/ IJCOT-V3I4P10
Abstract
Maximum clique problem is NP-hard problem which applies its application in determining the maximum connected sub graphs. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Clique corresponds to individual set in the graph. The approach used in obtaining maximum clique is Genetic Algorithm. Genetic Algorithms are a type of optimization algorithm which is based on the theory of natural selection for generating solutions of the problem. Genetic Algorithms are adaptive heuristic search algorithms for the survival of the fittest. The Genetic Algorithm is a probabilistic search algorithm that iteratively transforms a set of mathematical objects of fixed length binary string. The maximum clique problem calls for finding the maximum sized sub graphs in a particular graph. The intent is to develop a method to find the optimal solution from huge set of solutions.
Keywords
Jamming Attacks, Wireless Networks Elements, Crypto–logic Riddles, Enhanced Packet Delivery Techniques, wi-fi, Blue Tooth.
References
[2] R.Cruz and N. Lopez, A Neural Network Approach to Solve the Maximum Clique Problem, In Proceedings of the V European Congress on Intelligent Techniques and SoftComputing - EUFIT, Vol. 1, pp. 465-470, 1997.
[3] Coen Bron, Joep Kerbosch, Finding all cliques in an undirected graph, Communications of the ACM, Vol. 16, pp 575-577, 1973.
[4] James Cheng, Yiping Ke, Fast Algorithms for Maximal Clique Enumeration with Limited Memory, ACM 978-1- 4503-1462-6, 2012.
[5] David R. Wood, An Algorithm for Finding a Maximum Clique in a Graph, Operations Research Letters, Vol. 21 , pp. 211-217
[6] Panos M. Pardalos, A exact algorithm for the Maximum clique problem, Operations Research Letters, Vol. 9, pp 375- 382, 1990.
[7] Harsh Bhasin, R. Mahajan, Genetic Algorithm Based Solution to Maximum Clique Problem, International Journal of Computer Science and Engineering, Vol. 4, 2012.
[8] Harsh Bhasin, Gitanjali Ahuja, Harnessing Genetic Algorithm for Vertex Cover Problem, International Journal of Computer Science and Engineering, Vol. 4, 2012.
[9] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman,1979
[10] P.M. Pardalos and J. Xue, The Maximum Clique Problem, Journal of Global Optimization, Vol. 4, pp. 301-328, 1994.
[11] Etsuji Tomita, Hiroaki Nakanishi Polynomial Time solvability of the Maximum Clique problem, In Proceeding ECC'09 Proceedings of the 3rd international conference on European computing conference, pp 203-208.
[12] F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks,Vol. 3, pp. 261- 273, 1973.
[13] Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiment Journal Theoretical Computer Science, Computing and combinatorics, Vol. 363 , 2006.
[14] K. Makino, T. Uno, New algorithms for enumerating all maximal cliques, Lecture Notes in Computer Science, Vol. 3111, pp. 260-272, 2004.
[15] T. Nakagawa, E. Tomita, Experimental comparisons of algorithms for generating all maximal cliques, Technical Report of IPSJ, MPS-52, pp. 41-44, 2004
[16] Etsuji Tomita, Toshikatsu Kameda, An efficient Branch and Bound algorithm for finding a maximum clique with computational experiment, Journal of Global Optimization Vol. 37, pp. 95-111, 2007.
[17] Harsh Bhasin, Nishant Gupta, Randomized Algorithm Approach for Solving PCP, International Journal Of Computer Science and Engineering, Vol. 4, 2012.
[18] Harsh Bhasin, Neha Singla, Modified Genetic Algorithms Based Solution to Subset Sum Problem, International Journal of Advanced Research in Artificial Intelligence, Vol. 1, No. 1, 2012.
[19] Harsh Bhasin, Neha Singla, Genetic based Algorithm for N – Puzzle Problem, International Journal of Computer Applications, Vol. 51, No.22, 2012.
[20] Bhattacharya B.K,Kaller D, An O(m+nlogn) Algorithm for the Maximum clique problem in circular arc graphs, Journal of Algorithms, Volume 25 ,pp 336 – 358, 2007.
[21] Harsh Bhasin, Nakul Arora, Cryptography using Genetic Algorithms, In Reliability Infocom Technology and Optimization, Faridabad, 2010.