Embedding of Binomial Trees in Hypercubes with Link Faults

Authors: Wu J.; Fernandez E.B.; Luo Y.

Source: Journal of Parallel and Distributed Computing, Volume 54, Number 1, October 1998 , pp. 59-74(16)

Publisher: Academic Press

Buy & download fulltext article:

OR

Price: $52.63 plus tax (Refund Policy)

Abstract:

We study the embedding of binomial trees with variable roots in n-dimensional hypercubes (n-cubes) with faulty links. A simple embedding algorithm is first proposed that can embed an n-level binomial tree in an n-cube with up to n-1 faulty links in log(n-1) steps. We then extend the result to show that spanning binomial trees exist in a connected n-cube with up to lceil(3(n-1)/2)rceil-1 faulty links. A constructive proof is provided to locate spanning binomial trees in the given system. Our results reveal the fault tolerance property of hypercubes and they can be used to predict the performance of broadcasting and reduction operations, where the binomial tree structure is commonly used. Copyright 1998 Academic Press.

Language: English

Document Type: Research article

Affiliations: Department of Computer Science and Engineering, Florida Atlantic University, Boca Raton, Florida, 33431

Publication date: 1998-10-01

Related content

Tools

Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content

Text size:

A | A | A | A
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages. print icon Print this page