Ant colony optimization algorithm for finding the maximum number of d-size cliques in a graph with not all m edges between its d parts
Authors:
- Krzysztof Schiff
Abstract
A graph with m vertices in each of its d sections is a d-partite graph. In sections of a d-partite graph, the vertices are not connected by any edges. Each pair of vertices from different sections is always connected by an edge. If in a d-partite graph each section has m vertices, then such a graph can be divided into m d-vertex cliques if it has all edges between each pair of vertices from different sections. If in a graph with m vertices in each section there are no edges between each pair of vertices from different sections of the graph, then such a graph cannot be divided into m cliques. Such a graph can be easily divided into cliques, but their number does not have to be the maximum number of cliques into which such a graph can be divided. So this article deals with the problem of how to divide such a graph into cliques so that their number is the maximum number of cliques. For this purpose ant algorithms without and with two different dynamic desire function were used. The achieved results were compared and discussed.
- Record ID
- CUT4dd6688572994e2f96a28552f9607fa8
- Publication categories
- ; ;
- Author
- Pages
- 255-264
- Other elements of collation
- rys.; tab.; Bibliografia (liczba pozycji) - 12; Oznaczenie streszczenia - Abstr.
- Substantive notes
- Punktacja MNiSW/MEiN (rozdział) - 20
- Book
- Zamojski Wojciech, Wojciech Zamojski Mazurkiewicz Jacek, Jacek Mazurkiewicz Sugier Jarosław Jarosław Sugier [et al.] (eds.): Dependable Computer Systems and Networks : proceedings of the Eighteenth International Conference on Dependability of Computer Systems DepCoS-RELCOMEX, July 3-7, 2023, Brunów, Poland, Lecture Notes in Networks and Systems, vol. 737, 2023, Cham, Springer, 375 p., ISBN 978-3-031-37720-4. DOI:10.1007/978-3-031-37720-4 Opening in a new tab
- Keywords in English
- ant colony algorithm, d-partite graph, graph partitioning into cliques, maximum clique
- URL
- https://link.springer.com/chapter/10.1007/978-3-031-37720-4_23 Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 20
- Score source
- conferenceList
- Score
- Publication indicators
- = 0
- Additional fields
- Indeksowana w: CORE
- Uniform Resource Identifier
- https://cris.pk.edu.pl/info/article/CUT4dd6688572994e2f96a28552f9607fa8/
- URN
urn:pkr-prod:CUT4dd6688572994e2f96a28552f9607fa8
* 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.