کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332694 | 687746 | 2016 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounds on the cover time of parallel rotor walks
ترجمه فارسی عنوان
در زمان پوشش روتور موازی موثر است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the initialization of the walks. We show that for any graph with m edges and diameter D, this cover time is at most Î(mD/logâ¡k) and at least Î(mD/k), which corresponds to a speedup of between Î(logâ¡k) and Î(k) with respect to the cover time of a single walk.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 802-816
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 802-816
نویسندگان
Dariusz Dereniowski, Adrian Kosowski, Dominik PajÄ
k, PrzemysÅaw UznaÅski,