The NP-completeness of the road coloring problem

DOI10.1016/J.IPL.2010.12.016zbMATH Open1260.68162OpenAlexW2012090802MaRDI QIDQ1944896FDOQ1944896

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

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

Cited In (5)

• Approximating the minimum length of synchronizing words is hard
• Černý's conjecture and the road colouring problem
• 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
• 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)