P-NP threshold for synchronizing road coloring

DOI10.1007/978-3-642-28332-1_41MaRDI QIDQ2890221zbMATH OpenOpenAlexFDO

Authors 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

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) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• Decision Version of the Road Coloring Problem Is NP-Complete
• Parameterized complexity of synchronization and road coloring
• The road coloring problem

Cited in

(6)

• 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
• On the Number of Synchronizing Colorings of Digraphs
• A NOTE ON SYNCHRONIZED AUTOMATA AND ROAD COLORING PROBLEM
• Decision Version of the Road Coloring Problem Is NP-Complete
• Parameterized complexity of synchronization and road coloring

This page was built for publication: P-NP threshold for synchronizing road coloring

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