کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419049 | 681735 | 2014 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A quadratic algorithm for road coloring
ترجمه فارسی عنوان
الگوریتم درجه دوم برای رنگ آمیزی جاده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل رنگ آمیزی جاده، نمودارهای همزمان هماهنگ شده، هماهنگ سازی خودکار
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The Road Coloring Theorem states that every aperiodic directed graph with constant out-degree has a synchronized coloring. This theorem had been conjectured during many years as the Road Coloring Problem before being settled by A. Trahtman. Trahtman’s proof leads to an algorithm that finds a synchronized labeling with a cubic worst-case time complexity. We show a variant of his construction with a worst-case complexity which is quadratic in time and linear in space. We also extend the Road Coloring Theorem to the periodic case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 169, 31 May 2014, Pages 15–29
Journal: Discrete Applied Mathematics - Volume 169, 31 May 2014, Pages 15–29
نویسندگان
Marie-Pierre Béal, Dominique Perrin,