An Algorithm for Road Coloring

DOI10.1007/978-3-642-25011-8_28zbMath1315.68172OpenAlexW2108161663MaRDI QIDQ3111663

A. N. Trahtman

Publication date: 13 January 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25011-8_28

zbMATH Keywords

graph algorithmsynchronizationdeterministic finite automatonroad coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

An algorithm for road coloring ⋮ Complexity of road coloring with prescribed reset words ⋮ The NP-completeness of the road coloring problem ⋮ Sets of nonnegative matrices without positive products ⋮ A quadratic algorithm for road coloring ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ A complete solution to the complexity of synchronizing road coloring for non-binary alphabets

Uses Software

• TESTAS

This page was built for publication: An Algorithm for Road Coloring