Dense edge-disjoint embedding of complete binary trees in interconnection networks

We describe dense edge-disjoint embeddings of the complete binary tree with n leaves in the following n-node communication networks: the hypercube, th e de Bruijn and shuffle-exchange networks and the two-dimensional mesh. For the mesh and the shuffle-exchange graphs each edge is regarded as two para llel (or anti-parallel) edges. The embeddings have the following properties : paths of the tree are mapped onto edge-disjoint paths of the host graph a nd at most two tree nodes (just one of which is a leaf) are mapped onto eac h host node. We prove that the maximum distance from a leaf to the root of the tree is asymptotically as short as possible in all host graphs except i n the case of the shuffle-exchange, in which case we conjecture that it is as short as possible. The embeddings facilitate efficient implementation of many P-RAM algorithms on these networks. (C) 2000 Elsevier Science B.V. Al l rights reserved.