As the title states, this paper is about embedding an arbitrary binary tree into a hypercube. This problem is important because it is a generalization of the very practical problem of matching an algorithm’s communication pattern (the binary tree) to an existing architecture (the hypercube).

The proposed embedding algorithm improves previous boundaries for dilation, load, and expansion, simultaneously. The embedding is done deterministically online (dynamically), with the help of a quad tree known as (h,o,&tgr;)-tree. The (h,o,&tgr;)-tree has been previously mapped to the hypercube, and the binary tree is then embedded to the hypercube using the (h,o,&tgr;)-tree.

The proof is technical, and built upon the authors’, and others’, previous work. Some knowledge of the field is required in order to understand it.