کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6876267 689734 2013 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Gathering asynchronous oblivious agents with local vision in regular bipartite graphs
ترجمه فارسی عنوان
جمع آوری عوامل غیرمستقیم با چشم انداز محلی در نمودارهای منظم دو طرفه
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) The gathering problem is to determine which configurations are gatherable and find a (universal) algorithm which gathers all gatherable configurations. We give a complete solution of the gathering problem for regular bipartite graphs. Our main contribution is the proof that the class of gatherable initial configurations is very small: it consists only of “stars” (an agent A with all other agents adjacent to it) of size at least 3. On the positive side we give an algorithm accomplishing gathering for every gatherable configuration.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 509, 21 October 2013, Pages 86-96
نویسندگان
, ,