An algorithm for road coloring

DOI10.1016/J.JDA.2012.05.003MaRDI QIDQ1932365zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Software, source code, etc. for problems pertaining to computer science (68-04)

Recommendations

• An algorithm for road coloring
• The road coloring problem
• A partially synchronizing coloring
• A quadratic algorithm for road coloring
• scientific article; zbMATH DE number 2087221

Cites work

• scientific article; zbMATH DE number 177164 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1241365 (Why is no real title available?)
• scientific article; zbMATH DE number 1346363 (Why is no real title available?)
• scientific article; zbMATH DE number 1551726 (Why is no real title available?)
• scientific article; zbMATH DE number 1834666 (Why is no real title available?)
• scientific article; zbMATH DE number 846959 (Why is no real title available?)
• scientific article; zbMATH DE number 3354928 (Why is no real title available?)
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• A min-max theorem about the road coloring conjecture
• A note on the road-coloring conjecture
• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• An Introduction to Symbolic Dynamics and Coding
• An algorithm for road coloring
• Cycles of relatively prime length and the road coloring problem
• Decision Version of the Road Coloring Problem Is NP-Complete
• Depth-First Search and Linear Graph Algorithms
• Equivalence of topological Markov shifts
• Matrix Mortality and the Černý-Pin Conjecture
• On the Road Coloring Problem
• Similarity of automorphisms of the torus
• Slowly synchronizing automata and digraphs
• The Synchronization Problem for Strongly Transitive Automata
• The road coloring problem
• The road-colouring problem

Cited in

(6)

• On synchronizing colorings and the eigenvectors of digraphs
• scientific article; zbMATH DE number 1551726 (Why is no real title available?)
• An algorithm for road coloring
• A partially synchronizing coloring
• A quadratic algorithm for road coloring
• The road coloring problem

Describes a project that uses

Uses Software

• TESTAS

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

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