تقرير
How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm
| العنوان: | How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm |
|---|---|
| المؤلفون: | García-Altamirano, Juan Carlos, Olsen, Mika, Cervantes-Ojeda, Jorge |
| المصدر: | Discrete Mathematics & Theoretical Computer Science, vol. 25:1, Discrete Algorithms (March 1, 2023) dmtcs:10189 |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Artificial Intelligence, 05C20, 05C15, 68T20, 68W50 |
| الوصف: | In 2020 Bang-Jensen et. al. generalized the Haj\'os join of two graphs to the class of digraphs and generalized several results for vertex colorings in digraphs. Although, as a consequence of these results, a digraph can be obtained by Haj\'os constructions (directed Haj\'os join and identifying non-adjacent vertices), determining the Haj\'os constructions to obtain the digraph is a complex problem. In particular, Bang-Jensen et al. posed the problem of determining the Haj\'os operations to construct the symmetric 5-cycle from the complete symmetric digraph of order 3 using only Haj\'os constructions. We successfully adapted a rank-based genetic algorithm to solve this problem by the introduction of innovative recombination and mutation operators from graph theory. The Haj\'os Join became the recombination operator and the identification of independent vertices became the mutation operator. In this way, we were able to obtain a sequence of only 16 Haj\'os operations to construct the symmetric cycle of order 5. Comment: 11 pages, 5 figures, 6 algoritms |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.46298/dmtcs.10189 |
| URL الوصول: | http://arxiv.org/abs/2210.05080 |
| رقم الأكسشن: | edsarx.2210.05080 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.46298/dmtcs.10189 |
|---|