An algorithm for road coloring

DOI10.1007/978-3-642-25011-8_28MaRDI QIDQ3111663zbMATH OpenOpenAlexFDO

Authors A. N. Trahtman

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

zbMATH Keywords

graph algorithmsynchronizationdeterministic finite automatonroad coloring

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• An algorithm for road coloring
• A partially synchronizing coloring
• The road coloring problem
• A quadratic algorithm for road coloring
• scientific article; zbMATH DE number 2087221

Cited in

(11)

• scientific article; zbMATH DE number 1551726 (Why is no real title available?)
• Sets of nonnegative matrices without positive products
• An algorithm for road coloring
• A multi-parameter analysis of hard problems on deterministic finite automata
• The NP-completeness of the road coloring problem
• A partially synchronizing coloring
• A note on polynomial approximation of synchronizing optimal coloring
• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• Decision Version of the Road Coloring Problem Is NP-Complete
• A quadratic algorithm for road coloring
• The road coloring problem

Describes a project that uses

Uses Software

• TESTAS

This page was built for publication: An algorithm for road coloring

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