An Ant Algorithm for the Maximum Clique Problem in a Special Kind of Graph

• Autorzy: Schiff K.

Identyfikatory

DOI

10.14313/JAMRIS_2-2015/13

• Języki publikacji: EN

Abstrakty

EN

The maximum clique problem is a very well-known NP-complete problem of the kind for which meta-heuristic algorithms, which include ant algorithms, have been developed. Well-known instances of problems enable the assessment of the quality of elaborated algorithms; however, there is a particular kind of graph in which each vertex has a nearly equal number of adjacent edges. It is very difficult to find a maximum clique in such a graph. The search for the maximum clique in this particular kind of graph is investigated and compared to the best known ant algorithms.

Słowa kluczowe

EN

ant algorithm; maximum clique problem

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2015
• Tom: Vol. 9, No. 2
• Strony: 20--23
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology, ul. Warszawska 24, 31-155 Kraków, Poland

Bibliografia

• [1] Dorigo M. et al., “Ant algorithms for discrete optimization”, Artificial Life, vol. 5, no. 2, 1999, 137–172. DOI: 10.1162/106454699568728.
• [2] Fenet S., Solnon C., “Searching for maximum cliques with ant colony optimization”, Applications of Evolutionary Computing, LNCS 2611, Springer, 2003, 236–245. DOI: 10.1007/3-540-36605-9_22.
• [3] Karp R.M., “Reducibility among Combinatorial Problems”. In: Miller R.E. and Thatcher J.W. (ed.), Complexity of Computer Computation, Plenum Press, N.Y., 1972, 85–103. DOI: 10.1007/978-1-4684-2001-2.
• [4] Rizzo J.R., An Ant System Algorithm for Maximum Clique, Master’s Thesis, 2003, The Pennsylvania State University The Graduate School Capital College.
• [5] Thang N. et al., “Finding Maximum Cliques with Distributed Ants”. In: Deb K. et al. (eds.): GECCO 2004, LNCS 3102, 2004, 24–35.
• [6] Xinshun Xu et al., An Improved Ant Colony Optimization for the Maximum Clique Problem. In: Third International Conference on Natural Computation (ICNC 2007), vol. 4, 24–27 Aug. 2007, Haikou, 766–770. DOI: 10.1109/ICNC.2007.205.
• [7] Bui T.N., Rizzo J.R., “Finding Maximum Cliques with Distributed Ants”. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), Seattle, June 2004, Lecture Notes in Computer Science, vol. 3102, Springer-Verlag Heidelberg, pp. 24–35. DOI: 10.1007/978-3-540-24854-5_3.