کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430963 688238 2012 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An algorithm for road coloring
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
An algorithm for road coloring
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 16, October 2012, Pages 213–223
نویسندگان
,