A quadratic algorithm for road coloring

DOI10.1016/j.dam.2013.12.002zbMath1288.05080OpenAlexW1993902633MaRDI QIDQ2449052

Dominique Perrin, Marie-Pierre Béal

Publication date: 6 May 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.12.002

zbMATH Keywords

road coloring problemsynchronization of automatasynchronized directed graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (8)

Complexity of road coloring with prescribed reset words ⋮ The road problem and homomorphisms of directed graphs ⋮ All finite transitive graphs admit a self-adjoint free semigroupoid algebra ⋮ Černý's conjecture and the road colouring problem ⋮ Structure of free semigroupoid algebras ⋮ Unnamed Item ⋮ Synchronizing Almost-Group Automata ⋮ A complete solution to the complexity of synchronizing road coloring for non-binary alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generalized road coloring problem and periodic digraphs
• The road coloring problem
• Synchronization
• The road-colouring problem
• Equivalence of topological Markov shifts
• On the effects of noise and speed on computations
• Synchronizing finite automata on Eulerian digraphs.
• Expansive invertible onesided cellular automata
• The NP-completeness of the road coloring problem
• An Algorithm for Road Coloring
• Reset Sequences for Monotonic Automata
• Almost all complete binary prefix codes have a self-synchronizing string
• A Partially Synchronizing Coloring
• The Complexity of Finding Reset Words in Finite Automata
• Algorithms for sliding block codes - An application of symbolic dynamics to information theory
• On the Road Coloring Problem
• An Introduction to Symbolic Dynamics and Coding
• Random Generation of Deterministic Acyclic Automata Using the Recursive Method
• Cycles of relatively prime length and the road coloring problem

This page was built for publication: A quadratic algorithm for road coloring