✦ LIBER ✦
A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube
✍ Scribed by Volker Heun; Ernst W. Mayr
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 250 KB
- Volume
- 20
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 it desirable to simulate binary trees on a hypercube. In this paper, we present a simple one-to-one embedding of arbitrary binary trees into their optimal hypercubes with dilation 8 and constant node-congestion. The novelty of our method is the use of an intermediate quadtree data structure, which also permits the embedding to be efficiently computed on the hypercube itself.