Congestion-free, dilation-2 embedding of complete binary trees into star graphs

Trees are a common structure to represent the intertask communication patte rn of a parallel algorithm. In this paper, we consider the embedding of a c omplete binary tree in a star graph with the objective of minimizing conges tion and dilation. We develop two embeddings: (i) a congestion-free, dilati on-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 = Sigma(i=2)(n) [log i] = Omega(n log n) a nd k is any positive integer. The first result offers a tree of size compar able 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. (C) 1999 John Wiley & Sons, Inc.