Name
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 |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/71.210811 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
n-3 node,trees (mathematics),hypercubes,upper bound isfound,k-tree,fault tolerant computing,arbitrary number ofnodes,faulty hypercubes,computational complexity,simulation ofcomplete binary tree,simulation,fault-tolerant embedding,upper bound,fault tolerant embedding,graph-theoretic question,np-complete,following graph-theoretic question,complete binary trees,certain number,hypercube networks,binary trees,robustness,fault tolerant,helium,binary tree,np complete,fault tolerance,tree graphs,computer science,k tree,indexing terms | Discrete mathematics,NP-complete,K-tree,Upper and lower bounds,Computer science,Fault tolerant embedding,Binary tree,Theoretical computer science,Hypercube,Computational complexity theory,Distributed computing | Journal |
Volume | Issue | ISSN |
4 | 3 | 1045-9219 |
Citations | PageRank | References |
32 | 2.14 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Y. Chan | 1 | 32 | 2.14 |
| S. J. Lee | 2 | 195 | 13.79 |