Efficient Broadcasting in an Arrangement Graph Using Multiple Spanning Trees

Yuh-Shyan CHEN  Tong-Ying JUANG  En-Huai TSENG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A   No.1   pp.139-149
Publication Date: 2000/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
arrangement graph,  broadcast,  interconnection network,  parallel processing,  routing,  

Full Text: PDF(840.7KB)>>
Buy this Article

The arrangement graph An,k is not only a generalization of star graph (n-k=1), but also more flexible. Designing efficient broadcasting algorithm on a regular interconnection network is a fundamental issue for the parallel processing techniques. Two contributions are proposed in this paper. Initially, we elucidate a first result to construct n-k edge-disjoint spanning trees in an An,k. Second, we present efficient (one/all)-to-all broadcasting algorithms by using constructed n-k spanning trees, where height of each spanning tree is 2k-1. The arrangement graph is assumed to use one-port and all-port communication models and packet-switching (or store-and-forward) technique. Using n-k spanning trees allows us to present efficient broadcasting algorithm in the arrangement graphs and outperforms previous results. This is justified by our performance analysis.