✦ LIBER ✦

Dense edge-disjoint embedding of complete binary trees in the hypercube

✍ Scribed by Somasundaram Ravindran; Alan Gibbons

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 407 KB
Volume: 45
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(93)90044-a

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Link-disjoint embedding of complete bina

Link-disjoint embedding of complete binary trees in meshes

✍ Lee, Sang-Kyu; Choi, Hyeong-Ah 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB

We consider the problem of embedding complete binary trees into meshes with the objective of minimizing the link congestion. Gibbons and Paterson showed that a complete binary tree T p (with 2 p 0 1 nodes) can be embedded into a 2-dimensional mesh of 2 p nodes with link congestion two. Using the dim

Embedding All Binary Trees in the Hyperc

Embedding All Binary Trees in the Hypercube

✍ A.S. Wagner 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 923 KB

Optimal Dynamic Embeddings of Complete B

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes

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

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

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

Embedding the Complete Tree in the Hyper

Embedding the Complete Tree in the Hypercube

✍ A.S. Wagner 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 453 KB

Let \(H_{n}\) be the \(n\)-dimensional boolean hypercube with \(2^{n}\) vertices labeled \(\left\{0,1, \ldots 2^{n}-1\right\}\), with an edge between two vertices whenever their Hamming distance is 1. We describe a spanning tree \(T_{n}\) of \(H_{n}\) with the following properties. \(T_{n}\) is comp

Routing a Permutation in the Hypercube b

Routing a Permutation in the Hypercube by Two Sets of Edge Disjoint Paths

✍ Qian-Ping Gu; Hisao Tamaki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 95 KB

Consider a hypercube regarded as a directed graph, with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths.