P–NP Threshold for Synchronizing Road Coloring

DOI10.1007/978-3-642-28332-1_41zbMath1315.68157OpenAlexW106514942MaRDI QIDQ2890221

Adam Roman

Publication date: 8 June 2012

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28332-1_41

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

On the Number of Synchronizing Colorings of Digraphs ⋮ Complexity of road coloring with prescribed reset words ⋮ A multi-parameter analysis of hard problems on deterministic finite automata

This page was built for publication: P–NP Threshold for Synchronizing Road Coloring