Geodesic
How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.10189
Classification : 05C12, 05C20, 05C38, 05C76, 05C85 
@article{DMTCS_2023_25_1_a1,
     author = {Garc{\'\i}a-Altamirano, Juan Carlos and Olsen, Mika and Cervantes-Ojeda, Jorge},
     title = {How to construct the symmetric cycle of length 5 using {Haj\'os} construction with an adapted {Rank} {Genetic} {Algorithm}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2023-2024},
     doi = {10.46298/dmtcs.10189},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10189/}
}
TY  - JOUR
AU  - García-Altamirano, Juan Carlos
AU  - Olsen, Mika
AU  - Cervantes-Ojeda, Jorge
TI  - How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10189/
DO  - 10.46298/dmtcs.10189
LA  - en
ID  - DMTCS_2023_25_1_a1
ER  - 
%0 Journal Article
%A García-Altamirano, Juan Carlos
%A Olsen, Mika
%A Cervantes-Ojeda, Jorge
%T How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10189/
%R 10.46298/dmtcs.10189
%G en
%F DMTCS_2023_25_1_a1
García-Altamirano, Juan Carlos; Olsen, Mika; Cervantes-Ojeda, Jorge. How to construct the symmetric cycle of length 5 using Haj\'os construction with an adapted Rank Genetic Algorithm. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1. doi : 10.46298/dmtcs.10189. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10189/

Cité par Sources :