Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six
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 w...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2019/4073905 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832562663124631552 |
|---|---|
| author | J. Cervantes-Ojeda M. Gómez-Fuentes D. González-Moreno M. Olsen |
| author_facet | J. Cervantes-Ojeda M. Gómez-Fuentes D. González-Moreno M. Olsen |
| author_sort | J. Cervantes-Ojeda |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-2e50c490b3b946f19faaf18b104ce79c |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-2e50c490b3b946f19faaf18b104ce79c2025-02-03T01:22:08ZengWileyJournal of Applied Mathematics1110-757X1687-00422019-01-01201910.1155/2019/40739054073905Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth SixJ. Cervantes-Ojeda0M. Gómez-Fuentes1D. González-Moreno2M. Olsen3Universidad Autónoma Metropolitana, Cuajimalpa 05348, MexicoUniversidad Autónoma Metropolitana, Cuajimalpa 05348, MexicoUniversidad Autónoma Metropolitana, Cuajimalpa 05348, MexicoUniversidad Autónoma Metropolitana, Cuajimalpa 05348, MexicoA 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.http://dx.doi.org/10.1155/2019/4073905 |
| spellingShingle | J. Cervantes-Ojeda M. Gómez-Fuentes D. González-Moreno M. Olsen Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six Journal of Applied Mathematics |
| title | Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six |
| title_full | Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six |
| title_fullStr | Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six |
| title_full_unstemmed | Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six |
| title_short | Rainbow Connectivity Using a Rank Genetic Algorithm: Moore Cages with Girth Six |
| title_sort | rainbow connectivity using a rank genetic algorithm moore cages with girth six |
| url | http://dx.doi.org/10.1155/2019/4073905 |
| work_keys_str_mv | AT jcervantesojeda rainbowconnectivityusingarankgeneticalgorithmmoorecageswithgirthsix AT mgomezfuentes rainbowconnectivityusingarankgeneticalgorithmmoorecageswithgirthsix AT dgonzalezmoreno rainbowconnectivityusingarankgeneticalgorithmmoorecageswithgirthsix AT molsen rainbowconnectivityusingarankgeneticalgorithmmoorecageswithgirthsix |