کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
432483 688911 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
چکیده انگلیسی

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 70, Issue 4, April 2010, Pages 406–415
نویسندگان
, ,