The NP-completeness of the road coloring problem

DOI10.1016/j.ipl.2010.12.016zbMath1260.68162OpenAlexW2012090802MaRDI QIDQ1944896

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) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

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

Cites Work

• The road coloring problem
• Equivalence of topological Markov shifts
• An Algorithm for Road Coloring
• Decision Version of the Road Coloring Problem Is NP-Complete
• Reset Sequences for Monotonic Automata
• The Complexity of Finding Reset Words in Finite Automata
• Similarity of automorphisms of the torus

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