Multi-node broadcasting in an arrangement graph using multiple spanning trees
Yuh‐Shyan Chen, Tong‐Ying Juang, Ying-Ying Shen · 2002
The arrangement graph A/sub n,k/ is not only a generalization of the star graph (n-k=1), but is also more flexible. Designing an efficient routing algorithm on a regular interconnection network is a fundamental issue for parallel processing techniques. We elucidate the multi-node broadcasting problem in an all-port communication model on the arrangement graph. Our routing strategy is proposed by construction of 2(n-k) spanning trees, where the height of each spanning tree is 2k-1. We also extend the routing strategy to a one-to-all broadcasting algorithm. Using 2(n-k) spanning trees allows us to present efficient (one/multi)- node broadcasting algorithms in the arrangement graph. The arrangement graph is assumed to use one-port and all-port models and packet-switching (or store-and forward) technique. Moreover we show that our (one/multi)-node broadcasting algorithms outperform previous results in the literature. This is justified by our performance analysis.