Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six

Autor: J. Cervantes-Ojeda, M. Gómez-Fuentes, D. González-Moreno, M. Olsen
Jazyk: angličtina
Rok vydání: 2019
Předmět:
Zdroj: Journal of Applied Mathematics, Vol 2019 (2019)
Druh dokumentu: article
ISSN: 1110-757X
1687-0042
DOI: 10.1155/2019/4073905
Popis: A rainbow t-coloring of a t-connected graph G is an edge coloring such that for any two distinct vertices u and v of G there are at least t internally vertex-disjoint rainbow (u,v)-paths. In this work, we apply a Rank Genetic Algorithm to search for rainbow t-colorings of the family of Moore cages with girth six (t;6)-cages. We found that an upper bound in the number of colors needed to produce a rainbow 4-coloring of a (4;6)-cage is 7, improving the one currently known, which is 13. The computation of the minimum number of colors of a rainbow coloring is known to be NP-Hard and the Rank Genetic Algorithm showed good behavior finding rainbow t-colorings with a small number of colors.
Databáze: Directory of Open Access Journals
Externí odkaz:
Nepřihlášeným uživatelům se plný text nezobrazuje