An ant algorithm for the maximum number of 3-cliques in 3-partite graphs
Authors:
- Krzysztof Schiff
Abstract
The problem of finding the maximum number of dvertices 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.
- Record ID
- CUTdc2dc15af34543ec919561b13e6d3469
- Publication categories
- ;
- Author
- Journal series
- Control and Cybernetics, ISSN 0324-8569, [0484-8569]
- Issue year
- 2021
- Vol
- 50
- No
- 2
- Pages
- 347-358
- Other elements of collation
- rys.; tab.; wykr.; Bibliografia (na s.) - 358; Oznaczenie streszczenia - Abstr.; Numeracja w czasopiśmie - Vol. 50, No 2
- Substantive notes
- Brak źródła online
- Keywords in English
- ant colony optimization, three-partite graph, 3clique, combinatorial optimization, graph theory
- URL
- http://control.ibspan.waw.pl:3000/mainpage Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 40
- Publication indicators
- = 1
- Citation count
- 1
- Uniform Resource Identifier
- https://cris.pk.edu.pl/info/article/CUTdc2dc15af34543ec919561b13e6d3469/
- URN
urn:pkr-prod:CUTdc2dc15af34543ec919561b13e6d3469
* presented citation count is obtained through Internet information analysis, and it is close to the number calculated by the Publish or PerishOpening in a new tab system.