The NP-completeness of the road coloring problem

DOI10.1016/J.IPL.2010.12.016MaRDI QIDQ1944896zbMATHOpenAlexFDO

Authors Adam Roman

Publication date 28 March 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.12.016

zbMATH Keywords

computational complexitysynchronizationroad coloring problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Cites work

• An algorithm for road coloring
• Decision Version of the Road Coloring Problem Is NP-Complete
• Equivalence of topological Markov shifts
• Reset Sequences for Monotonic Automata
• Similarity of automorphisms of the torus
• The complexity of finding reset words in finite automata
• The road coloring problem

Cited in

(4)

• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• Černý's conjecture and the road colouring problem
• A multi-parameter analysis of hard problems on deterministic finite automata
• A quadratic algorithm for road coloring

This page was built for publication: The NP-completeness of the road coloring problem

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