An algorithm for road coloring

DOI10.1016/j.jda.2012.05.003zbMath1262.68095OpenAlexW2568288801MaRDI 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

graphsynchronizationdeterministic finite automatonroad coloring

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Software, source code, etc. for problems pertaining to computer science (68-04)

Uses Software

• TESTAS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: An algorithm for road coloring