A New Efficient Algorithm for Embedding an Arbitrary Binary Tree
into Its Optimal Hypercube
The d-dimensional binary hypercube is a very popular model of parallel
computation. On the other hand, the execution of many algorithms can
be represented by binary trees, making desirable fast simulations of
binary trees on hypercubes. In this paper, we present a simple
one-to-one embedding of arbitrary binary trees into their optimal
hypercubes with dilation 8 and constant congestion. The novelty of
our method is based on the use of an intermediate quadtree data
structure, which also permits the embedding to be efficiently computed
on the hypecube itself.
