EMBEDDING OF K-ARY COMPLETE TREES INTO HYPERCUBES WITH UNIFORM LOAD

The main result of this paper is an algorithm for embedding k-ary comp lete trees into hypercubes with uniform load and asymptotically optima l dilation. The algorithm is fully scalable-the dimension of the hyper cube can be chosen independent of the arity and height of the tree. Th e embedding enables to emulate optimally both Divide&Conquer computati ons on k-ary complete trees where only one level of nodes is active at a time and general computations based on k-ary complete trees where a ll tree nodes are active simultaneously. As a special case, we get an algorithm for embedding the k-ary complete tree of given height into i ts optimal hypercube with load 1 and asymptotically optimal dilation. (C) 1998 Academic Press, Inc.