An algorithm for road coloring

详细信息    查看全文

• 作者：A.N. Trahtman
• 关键词：Algorithm ; Road coloring ; Graph ; Deterministic finite automaton ; Synchronization
• 刊名：Journal of Discrete Algorithms
• 出版年：2012
• 出版时间：October, 2012
• 年：2012
• 卷：16
• 期：Complete
• 页码：213-223
• 全文大小：192 K

文摘

A coloring of edges of a finite directed graph turns the graph into a finite-state automaton. A synchronizing word of a deterministic automaton is a word in the alphabet of colors of its edges (regarded as letters) which maps the automaton to a single state. A coloring of edges of a directed graph of uniform outdegree (constant outdegree of any vertex) is synchronizing if the corresponding deterministic finite automaton possesses a synchronizing word.

The road coloring problem is the problem of synchronizing coloring of a directed finite strongly connected graph of uniform outdegree if the greatest common divisor of lengths of all its cycles is one. Posed in 1970, it has evoked noticeable interest among the specialists in the theory of graphs, automata, codes, symbolic dynamics, and well beyond these areas.

We present an algorithm for the road coloring of cubic worst-case time complexity and quadratic time complexity in the majority of studied cases. It is based on the recent positive solution of the road coloring problem. The algorithm was implemented in the freeware package TESTAS.