Skip to Main content Skip to Navigation
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [30 references]  Display  Hide  Download
Contributor : Marie-Pierre Béal Connect in order to contact the contributor
Submitted on : Thursday, May 30, 2013 - 6:04:28 PM
Last modification on : Friday, September 16, 2022 - 1:51:27 PM
Long-term archiving on: : Saturday, August 31, 2013 - 8:40:07 AM


Files produced by the author(s)



Marie-Pierre Béal, Dominique Perrin. A quadratic algorithm for road coloring. Discrete Applied Mathematics, Elsevier, 2014, 169 (-), pp.15-29. ⟨10.1016/j.dam.2013.12.002⟩. ⟨hal-00627821v2⟩



Record views


Files downloads