Decision Version of the Road Coloring Problem Is NP-Complete
DOI10.1007/978-3-642-03409-1_26zbMath1252.68183OpenAlexW1568989345MaRDI QIDQ3183619
Publication date: 20 October 2009
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03409-1_26
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
This page was built for publication: Decision Version of the Road Coloring Problem Is NP-Complete