On directed edge-disjoint spanning trees in product networks, an algorithmic approach

In (Ku et al. 2003), the authors have proposed a construction of edge-disjoint spanning trees EDSTs in undirected product networks. Their construction method focuses more on showing the existence of a maximum number (n1+n2-1) of EDSTs in product network of two graphs, where factor graphs have respec...

Full description

Saved in:
Bibliographic Details
Published in:The journal of engineering research (Print) 2014-12, Vol.11 (2), p.79-88
Main Authors: Touzene, Abd al-Razzaq, Day, Khalid
Format: Article
Language:English
Subjects:
Computer networks
Graph theory
Multiprocessors
product networks, directed edge-disjoint spanning trees, interconnection networks
الاتصالات الرقمية
الاتصالات السلكية و اللاسلكية
شبكات الحاسوب
شبكات المعلومات
معالجة البيانات
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In (Ku et al. 2003), the authors have proposed a construction of edge-disjoint spanning trees EDSTs in undirected product networks. Their construction method focuses more on showing the existence of a maximum number (n1+n2-1) of EDSTs in product network of two graphs, where factor graphs have respectively n1 and n2 EDSTs. In this paper, we propose a new systematic and algorithmic approach to construct (n1+n2) directed routed EDST in the product networks. The direction of an edge is added to support bidirectional links in interconnection networks. Our EDSTs can be used straightforward to develop efficient collective communication algorithms for both models store-and-forward and wormhole. اقترح المؤلفون بناء للهيكل الممتد للحدود المنفصلة EDSTs لإنتاج شبكات غير موجهة. طريقة البناء لديهم تركز أكثر على إظهار وجود الرقم الأقصى (1-₂n+₁n) لأنظمة EDST في إنتاج الشبكات لرسمين بيانيين حيث معامل الرسومات على الترتيب 1n و EDST2n. في هذه المقالة نقدم مقترح لمنهج و نظام حسابي جديد لبناء (₂n+₁n) مسار موجهه EDSTs في منتج الشبكات. تم إضافة اتجاه الحد لدعم الروابط الثنائية لشبكات الربط. نظام EDSTs الخاص بنا يمكن استخدامه مباشرة لتطوير خوارزميات الاتصالات الجماعية الفعالة لكل من نموذجي التخزين إلى الأمام و الثقب.
ISSN:1726-6009
1726-6742
DOI:10.24200/tjer.vol11iss2pp79-88