کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333460 | 688970 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Edge-disjoint spanning trees for the generalized butterfly networks and their applications
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The generalized butterfly GBN(d,n) has recently gained some interest as a point-to-point interconnection network rather than the well known multi-stage butterfly networks. We construct edges-disjoint spanning trees (abbreviated EDSTs) for the GBN(d,n). Our construction is based on the decomposition of the GBN(d,n) into dn vertex-disjoint cycles of length n. As an application, we propose an efficient broadcasting algorithm and its fault-tolerant version for the GBN(d,n). Our fault-tolerant broadcasting algorithm is optimal in terms of fault-tolerance, because it resists 2d-1 edge failures (2d is the degree of the GBN(d,n)). We also propose an efficient scattering algorithm and its fault-tolerant version which resists 2d-3 edge faults.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 65, Issue 11, November 2005, Pages 1384-1396
Journal: Journal of Parallel and Distributed Computing - Volume 65, Issue 11, November 2005, Pages 1384-1396
نویسندگان
Abderezak Touzene, Khaled Day, Burkhard Monien,