Author(s)

Yuh-Shyan Chen, En-Huai Tseng, & Tong-Ying Juang

Abstract

Efficient broadcasting in an arrangement graph using multiple spanning trees* Yuh-Shyan Chen*, En-Huai Tseng*, & Tong-Ying Juang" 'Department of Computer Science and Information Engineering, Chung-Hua University, Taiwan -Department of Statistics, National Chung Hsing University, Taiwan Abstract The arrangement graph A^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 tech- niques. Two contributions are proposed in this paper. Initially, we elucidate a first result to construct n - k edge-disjoint spanning trees in an A^k- Second, we present an efficient broadcasting algorithm by using constructed n — k spanning trees, where height of each spanning tree is 2k — 1. The arrangement graph is as- sumed to use one-port and all-port communication models and packet-switching (or store-and-forward) techniq

Keywords