An ant algorithm for the maximum number of 3-cliques in 3-partite graphs

• Autorzy: Schiff Krzysztof
• Języki publikacji: EN

Abstrakty

EN

The problem of finding the maximum number of d- vertices cliques (d = 3) in d-partite graph (d = 3) when graph density q is lower than 1 is an important problem in combinatorial optimization and it is one of many NP-complete problems. For this problem a meta-heuristic algorithm has been developed, namely an ant colony optimization algorithm. In this paper a new development of this ant algorithm and experimental results are presented. The problem of finding the maximum number of 3-vertices cliques can be encountered in computer image analysis, computer vision applications, automation and robotic vision systems. The optimal solution of this problem boils down to finding a set of 3-vertices cliques in a 3-partite graph and this set should have cardinality as high as possible. The elaborated ant colony algorithm can be easily modified for d-dimensional problems, that is for finding the maximum number of d-vertices cliques in a d-partite graph.

Słowa kluczowe

EN

ant colony optimization; three-partite graph; 3-clique; combinatorial optimization; graph theory

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2021
• Tom: Vol. 50, No. 2
• Strony: 347--358
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Schiff Krzysztof

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

Bibliografia

• Biro, P. and McDemid, E. (2010) Three-sided stable matching with cyclic preferences. Algorithmica, 58, 1, 5-18.
• Chen, J. (2012) Iterative expansion and Color Coding: an Improved Algorithm for 3D-Matching. ACM Transactions on Algorithms, 6.1-6.22.
• Dorigo, M., Di Caro, G. and Gambardella, L. M. (1999) Ant algorithms for discrete optimization. Artificial Life, 5, 2, 137–172.
• Eriksson, K., Sj¨ostrand, J. and Strimling, P. (2006) Three-dimensional stable matching with cyclic preferences. Mathematical Social Sciences, 52, 1, 77-87.
• Karp, R.M. (1972) Reducibility among Combinatorial Problems. In: R. E. Miller and J. W. Thatcher, eds., Complexity of Computer Computation. Plenum Press, N.Y., 85-103.
• Knuth, D. (1997) Stable marriage and its relation to other combinatorial problems: An introduction to the mathematical analysis of algorithms. Amer. Math. Soc., Providence, RI.
• Schiff, K. (2018) An ant algorithmfor the triple matching problem. Technical Transactions, Electrical Engineering, 115, 2, 179-186.
• Schiff, K. (2020) An improved ant algorithm for the triple matching problem. Technical Transactions, 13, 1, art no. 20200005, 1-7.