<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The problem of finding the maximum number of d-vertices cliques (<italic>d</italic> = 3) in <italic>d</italic>-partite graph (<italic>d</italic> = 3) when graph density <italic>q</italic> 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.</p>
</abstract>

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.

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

Department of Automatic Control and Computer Science, Faculty of Electrical and Computer Engineering

Control and Cybernetics

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"An ant algorithm for the maximum number of 3-cliques in 3-partite graphs"}

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...

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

Publié en ligne: 28 juin 2022

Pages: 347 - 358

Reçu: 01 déc. 2020

Accepté: 01 févr. 2021

DOI: https://doi.org/10.2478/candc-2021-0018

Mots clés
ant colony optimization, three-partite graph, 3-clique, combinatorial optimization, graph theory

© 2021 Krzysztof Schiff, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

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

Publié en ligne: 28 juin 2022

Pages: 347 - 358

Reçu: 01 déc. 2020

Accepté: 01 févr. 2021

DOI: https://doi.org/10.2478/candc-2021-0018

Mots clésant colony optimization, three-partite graph, 3-clique, combinatorial optimization, graph theory

© 2021 Krzysztof Schiff, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
ant colony optimization, three-partite graph, 3-clique, combinatorial optimization, graph theory