ملخص
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.
اللغة الأصلية | English |
---|---|
الصفحات (من إلى) | 1384-1396 |
عدد الصفحات | 13 |
دورية | Journal of Parallel and Distributed Computing |
مستوى الصوت | 65 |
رقم الإصدار | 11 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | Published - نوفمبر 2005 |
ASJC Scopus subject areas
- ???subjectarea.asjc.1700.1712???
- ???subjectarea.asjc.2600.2614???
- ???subjectarea.asjc.1700.1708???
- ???subjectarea.asjc.1700.1705???
- ???subjectarea.asjc.1700.1702???