An algorithm for road coloring

DOI10.1016/j.jda.2012.05.003zbMath1262.68095MaRDI QIDQ1932365

A. N. Trahtman

Publication date: 18 January 2013

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2012.05.003

zbMATH Keywords

graph; synchronization; deterministic finite automaton; road coloring

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

68-04: Software, source code, etc. for problems pertaining to computer science

Uses Software

• TESTAS

Cites Work

• The road coloring problem
• The road-colouring problem
• Equivalence of topological Markov shifts
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
• An Algorithm for Road Coloring
• Decision Version of the Road Coloring Problem Is NP-Complete
• The Synchronization Problem for Strongly Transitive Automata
• Slowly Synchronizing Automata and Digraphs
• Matrix Mortality and the Černý-Pin Conjecture
• On the Road Coloring Problem
• An Introduction to Symbolic Dynamics and Coding
• Similarity of automorphisms of the torus
• Depth-First Search and Linear Graph Algorithms
• Cycles of relatively prime length and the road coloring problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item