Congestion-free, dilation-2 embedding of complete binary trees into star graphs
✍ Scribed by Tseng, Yu-Chee; Chen, Yuh-Shyan; Juang, Tong-Ying; Chang, Chiou-Jyu
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 291 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion-free, dilation-2, load-1 embedding of a level-p binary tree, and (ii) a congestion-free, dilation-2, load-2 k embedding of a level-( p ϩ k) binary tree, into an n-dimensional star graph, where p ϭ ¥ iϭ2 n log i ϭ ⍀(n log n) and k is any positive integer. The first result offers a tree of size comparable or superior to existing results, but with less congestion and dilation. The second result provides more flexibility in the embeddable tree sizes compared to existing results.