An Algorithm for Road Coloring
From MaRDI portal
Publication:3111663
DOI10.1007/978-3-642-25011-8_28zbMath1315.68172MaRDI QIDQ3111663
Publication date: 13 January 2012
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-25011-8_28
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Sets of nonnegative matrices without positive products, An algorithm for road coloring, The NP-completeness of the road coloring 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, Complexity of road coloring with prescribed reset words, A quadratic algorithm for road coloring
Uses Software