A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube

Volker Heun, Ernst W. Mayr

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

16 Zitate (Scopus)

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.

OriginalspracheEnglisch
Seiten (von - bis)375-399
Seitenumfang25
FachzeitschriftJournal of Algorithms
Jahrgang20
Ausgabenummer2
DOIs
PublikationsstatusVeröffentlicht - März 1996

Fingerprint

Untersuchen Sie die Forschungsthemen von „A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren