Technical Reports

The ICICS/CS Reading Room

UBC CS TR-90-34 Summary

Embedding All Binary Trees in the Hypercube, January 1990 Alan S. Wagner

An ${\cal O} (N^{2})$ heuristic algorithm is presented that embeds all binary trees, with dilation 2 and small average dilation, into the optimal sized hypercube. The heuristic relies on a conjecture about all binary trees with a perfect matching. It provides a practical and robust technique for mapping binary trees into the hypercube and ensures that the communication load is evenly distributed across the network assuming any shortest path routing strategy. One contribution of this work is the identification of a rich collection of binary trees that can be easily mapped into the hypercube.

If you have any questions or comments regarding this page please send mail to