 |
HAL UPEC - UPEM Portal |  |
 |
Journal articles
A quadratic algorithm for road coloring
Abstract : The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtman's proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
Cited literature [30 references]
https://hal-upec-upem.archives-ouvertes.fr/hal-00627821
Contributor : Marie-Pierre Béal <>
Submitted on : Thursday, May 30, 2013 - 6:04:28 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Saturday, August 31, 2013 - 8:40:07 AM
Contributor : Marie-Pierre Béal <>
Submitted on : Thursday, May 30, 2013 - 6:04:28 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Saturday, August 31, 2013 - 8:40:07 AM
Files
roadJournalV3.pdf
Files produced by the author(s)