✦ LIBER ✦

Embedding of Binomial Trees in Hypercubes with Link Faults

✍ Scribed by Jie Wu; Eduardo B. Fernandez; Yingqiu Luo

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 505 KB
Volume: 54
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.1998.1482

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Embedding paths of variable lengths into

Embedding paths of variable lengths into hypercubes with conditional link-faults

✍ Tz-Liang Kueng; Cheng-Kuan Lin; Tyne Liang; Jimmy J.M. Tan; Lih-Hsing Hsu 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 432 KB

Faults in a network may take various forms such as hardware failures while a node or a link stops functioning, software errors, or even missing of transmitted packets. In this paper, we study the link-fault-tolerant capability of an n-dimensional hypercube (n-cube for short) with respect to path emb

Fault-tolerant cycles embedded in hyperc

Fault-tolerant cycles embedded in hypercubes with mixed link and node failures

✍ Chang-Hsiung Tsai 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 282 KB

Let f e (respectively, f v ) denote the number of faulty edges (respectively, vertices) of an n-dimensional hypercube Q n . In this paper, we prove that every fault-free edge of Q n for n ≥ 3 lies on a fault-free cycle of every even length from 4 to 2 n -2 f v inclusive if f e + f v ≤ n -2. Furtherm

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 distributed algorithm for embedding tr

A distributed algorithm for embedding trees in hypercubes with modifications for run-time fault tolerance

✍ Foster J. Provost; Rami Melhem 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 588 KB

In this paper we present a distributed algorithm for embedding binary trees in hypercubes. Starting with the root (invoked in some cube node by a host), each node is responsible for determining the addresses of its children, and for invoking the embedding algorithm for the subtree rooted at each chi

Distributed fault-tolerant embeddings of

Distributed fault-tolerant embeddings of rings in hypercubes

✍ Mee Yee Chan; Shiang-Jen Lee 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 881 KB

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