An algorithm for road coloring

DOI10.1007/978-3-642-25011-8_28zbMATH Open1315.68172OpenAlexW2108161663MaRDI QIDQ3111663FDOQ3111663

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

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

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)

Cited In (12)

• Title not available (Why is that?)
• Sets of nonnegative matrices without positive products
• Complexity of road coloring with prescribed reset words
• An algorithm for road coloring
• A multi-parameter analysis of hard problems on deterministic finite automata
• A note on polynomial approximation of synchronizing optimal coloring
• The NP-completeness of the road coloring problem
• A partially synchronizing 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

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)