✦ LIBER ✦

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes

✍ Scribed by Volker Heun; Ernst W. Mayr

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 242 KB
Volume: 61
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.2001.1734

No coin nor oath required. For personal study only.

✦ Synopsis

It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf spawns two new leaves. In this paper, we present simple dynamic embeddings of double-rooted complete binary trees into hypercubes which do not suffer from this disadvantage. We also present edge-disjoint embeddings with optimal load and unit dilation. Furthermore, all these embeddings can be efficiently implemented on the hypercube itself such that the embedding of each new level of leaves can be computed in constant time. Because of the similarity, our results can be immediately transfered to complete binary trees.

📜 SIMILAR VOLUMES

Efficient Dynamic Embeddings of Binary T

Efficient Dynamic Embeddings of Binary Trees into Hypercubes

✍ Volker Heun; Ernst W. Mayr 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 255 KB

In this paper, a deterministic algorithm for dynamically embedding binary trees into hypercubes is presented. Because of a known lower bound, any such algorithm must use either randomization or migration, i.e., remapping of tree vertices, to obtain an embedding of trees into hypercubes with small di

Optimal Embedding of Complete Binary Tre

Optimal Embedding of Complete Binary Trees into Lines and Grid

✍ Ralf Heckmann; Ralf Klasing; Burkhard Monien; Walter Unger 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 179 KB

Embedding Large Complete Binary Trees in

Embedding Large Complete Binary Trees in Hypercubes with Load Balancing

✍ Kemal Efe 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 211 KB

In the next section we present basic definitions and notations where the criterion of optimality is defined and related to the concept of ''normal'' algorithms. In Section 3 we present an optimal embedding method that balances the processor loads. In Section 4 we present a nonoptimal embedding metho

A New Efficient Algorithm for Embedding

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

✍ Volker Heun; Ernst W. Mayr 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 250 KB

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 arbitrar

Embedding ofk-ary Complete Trees into Hy

Embedding ofk-ary Complete Trees into Hypercubes with Uniform Load

✍ Jan Trdlička; Pavel Tvrdı&#x0301;k 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 411 KB

Congestion-free, dilation-2 embedding of

Congestion-free, dilation-2 embedding of complete binary trees into star graphs

✍ Tseng, Yu-Chee; Chen, Yuh-Shyan; Juang, Tong-Ying; Chang, Chiou-Jyu 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 291 KB 👁 2 views

Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion-free, dilati