DocumentCode :
887147
Title :
Fault-tolerant embedding of complete binary trees in hypercubes
Author :
Chan, Mee Yee ; Lee, Shiang-Jen
Author_Institution :
Texas Univ., Dallas, TX, USA
Volume :
4
Issue :
3
fYear :
1993
fDate :
3/1/1993 12:00:00 AM
Firstpage :
277
Lastpage :
288
Abstract :
The focus is on the following graph-theoretic question associated with the simulation of complete binary trees by faulty hypercubes: if a certain number of nodes or links are removed from an n-cube, will an (n-1)-tree still exists as a subgraph? While the general problem of determining whether a k-tree, k< n, still exists when an arbitrary number of nodes/links are removed from the n-cube is found to be NP-complete, an upper bound is found on how many nodes/links can be removed and an (n-1)-tree still be guaranteed to exist. In fact, as a corollary of this, it is found that if no more than n-3 nodes/links are removed from an (n-1)-subcube of the n-cube, an (n-1)-tree is also guaranteed to exist
Keywords :
computational complexity; fault tolerant computing; hypercube networks; trees (mathematics); NP-complete; complete binary trees; fault tolerant embedding; graph-theoretic question; hypercubes; k-tree; simulation; upper bound; Binary trees; Computer science; Fault tolerance; Helium; Hypercubes; Robustness; Tree graphs;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.210811
Filename :
210811
Link To Document :
بازگشت