DENSE EDGE-DISJOINT EMBEDDING OF COMPLETE BINARY-TREES IN THE HYPERCUBE

We show that the complete binary tree with n > 8 leaves can be embedde d in the hypercube with n nodes such that: paths of the tree are mappe d onto edge-disjoint paths of the hypercube, at most two tree nodes (o ne of which is a leaf) are mapped onto each hypercube node, and the ma ximum distance from a leaf to the root of the tree is log2n + 1 hyperc ube edges (which is optimally short). This embedding facilitates effic ient implementation of many P-RAM algorithms on the hypercube.