- Tytuł:
- An ant algorithm for the maximum number of 3-cliques in 3-partite graphs
- Autorzy:
- Schiff, Krzysztof
- Powiązania:
- https://bibliotekanauki.pl/articles/2183443.pdf
- Data publikacji:
- 2021
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
ant colony optimization
three-partite graph
3-clique
combinatorial optimization
graph theory - Opis:
- 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.
- Źródło:
-
Control and Cybernetics; 2021, 50, 2; 347--358
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł