کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433068 689225 2012 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Efficient transformation of distance-2 self-stabilizing algorithms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Efficient transformation of distance-2 self-stabilizing algorithms
چکیده انگلیسی

Self-stabilizing algorithms for optimization problems can often be solved more easily using the distance-two model in which each vertex can instantly see the state information of all vertices up to distance two. This paper presents a new technique to emulate algorithms for the distance-two model on the distance-one model using the distributed scheduler with a slowdown factor of O(m)O(m) moves. Up until now the best transformer had a slowdown factor of O(n2m)O(n2m) moves. The technique is used to derive improved self-stabilizing algorithms for several graph domination problems. The paper also introduces a generalization of the distance-two model allowing a more space efficient transformer.


► New technique to emulate algorithms for the distance-two model.
► New execution model for self-stabilizing algorithms: expression model.
► Reduced the slowdown factor from O(n2m)O(n2m) to O(m)O(m) moves.
► Improved time and space complexity of transformer.
► Self-stabilizing algorithms for several graph domination problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 72, Issue 4, April 2012, Pages 603–612
نویسندگان
,