Abstract
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.
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 375-399 |
Seitenumfang | 25 |
Fachzeitschrift | Journal of Algorithms |
Jahrgang | 20 |
Ausgabenummer | 2 |
DOIs | |
Publikationsstatus | Veröffentlicht - März 1996 |