An Algorithm for Road Coloring

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

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)

Cited In (8)

• 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
• The NP-completeness of the road coloring problem
• A complete solution to the complexity of synchronizing road coloring for non-binary alphabets
• A quadratic algorithm for road coloring

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)