کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426072 685991 2013 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fault-tolerant compact routing schemes for general graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Fault-tolerant compact routing schemes for general graphs
چکیده انگلیسی

This paper considers compact fault-tolerant routing schemes for weighted general graphs, namely, routing schemes that avoid a set of failed (or forbidden) edges. We present a compact routing scheme capable of handling multiple edge failures. Assume a source node s contains a message M designated to a destination target t and assume a set F of edges crashes (unknown to s). Our scheme routes the message to t (provided that s and t   are still connected in G∖FG∖F) over a path whose length is proportional to the distance between s and t   in G∖FG∖F, to |F|3|F|3 and to some poly-log factor. The routing table required at a node v is of size proportional to the degree of v in G and some poly-log factor. This improves on the previously known fault-tolerant compact routing scheme for general graphs, which was capable of overcoming at most 2 edge failures.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 222, January 2013, Pages 36–44
نویسندگان
,