A quadratic algorithm for road coloring

DOI10.1016/J.DAM.2013.12.002MaRDI QIDQ2449052zbMATH OpenOpenAlexFDO

Authors Marie-Pierre Béal, Dominique Perrin

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

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

Recommendations

• An algorithm for road coloring
• An algorithm for road coloring
• A vector space approach to the road coloring problem
• The road coloring problem
• scientific article; zbMATH DE number 1551726
• Algorithms for coloring quadtrees
• A note on the road-coloring conjecture
• A Colored Path Problem and Its Applications
• A min-max theorem about the road coloring conjecture
• Černý's conjecture and the road colouring problem

Cites work

• A partially synchronizing coloring
• Algorithms for sliding block codes - An application of symbolic dynamics to information theory
• Almost all complete binary prefix codes have a self-synchronizing string
• An algorithm for road coloring
• An Introduction to Symbolic Dynamics and Coding
• Codes and automata.
• Cycles of relatively prime length and the road coloring problem
• Distribution of the number of accessible states in a random deterministic automaton
• Equivalence of topological Markov shifts
• Expansive invertible onesided cellular automata
• scientific article; zbMATH DE number 177164 (Why is no real title available?)
• scientific article; zbMATH DE number 3561239 (Why is no real title available?)
• scientific article; zbMATH DE number 1241365 (Why is no real title available?)
• scientific article; zbMATH DE number 2087221 (Why is no real title available?)
• On the effects of noise and speed on computations
• On the Road Coloring Problem
• Random generation of deterministic acyclic automata using the recursive method
• Reset Sequences for Monotonic Automata
• Synchronization
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing random automata
• The complexity of finding reset words in finite automata
• The NP-completeness of the road coloring problem
• The road coloring problem
• The road-colouring problem

Cited in

(14)

• An algorithm for road coloring
• Černý's conjecture and the road colouring problem
• Structure of free semigroupoid algebras
• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• A note on the road-coloring conjecture
• An algorithm for road coloring
• A min-max theorem about the road coloring conjecture
• scientific article; zbMATH DE number 1185607 (Why is no real title available?)
• On the Road Coloring Problem
• All finite transitive graphs admit a self-adjoint free semigroupoid algebra
• A note on polynomial approximation of synchronizing optimal coloring
• Synchronizing almost-group automata
• Cycles of relatively prime length and the road coloring problem
• The road problem and homomorphisms of directed graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2449052)