تقرير
Enumerating All Maximal Clique-Partitions of an Undirected Graph
| العنوان: | Enumerating All Maximal Clique-Partitions of an Undirected Graph |
|---|---|
| المؤلفون: | Marin, Mircea, Kutsia, Temur, Pau, Cleo, Rukhaia, Mikheil |
| المصدر: | EPTCS 389, 2023, pp. 65-79 |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, G2.1, G2.2 |
| الوصف: | We address the problem of enumerating all maximal clique-partitions of an undirected graph and present an algorithm based on the observation that every maximal clique-partition can be produced from the maximal clique-cover of the graph by assigning the vertices shared among maximal cliques, to belong to only one clique. This simple algorithm has the following drawbacks: (1) the search space is very large; (2) it finds some clique-partitions which are not maximal; and (3) some clique-partitions are found more than once. We propose two criteria to avoid these drawbacks. The outcome is an algorithm that explores a much smaller search space and guarantees that every maximal clique-partition is computed only once. The algorithm can be used in problems such as anti-unification with proximity relations or in resource allocation tasks when one looks for several alternative ways to allocate resources. Comment: In Proceedings FROM 2023, arXiv:2309.12959 |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.4204/EPTCS.389.6 |
| URL الوصول: | http://arxiv.org/abs/2309.13800 |
| رقم الأكسشن: | edsarx.2309.13800 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.4204/EPTCS.389.6 |
|---|