Name
Abstract | ||
|---|---|---|
The n-cube network is called faulty if it contains any faulty processor or any faulty link. For any number k we want to compute the minimum number f(n, k) of faults which is necessary for an adversary to make every (n - k)-dimensional subcube faulty. Reversely formulated: The existence of an (n - k)-dimensional non-faulty subcube can be guaranteed, if there are less than f(n, k) faults in the n-cube. In this paper several lower and upper bounds for f(n, k) are derived such that the resulting gaps are ''small.'' For instance if k = 2 is constant, then f(n, k) = @q(logn). Especially for k = 2 and large n: f(n, 2) @? [[@a"n@?]: [@a"n]@? + 2], where @a"n =logn + 1/2 log log n + 1/2. Or if k = @w(log log n) then 2^k |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1016/0890-5401(88)90056-9 | SFCS '86 Proceedings of the 27th Annual Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
log log n,faulty link,n-cube network,dimensional non-faulty subcube,number k,faulty processor,minimum number,large n,upper bound,robustness,artificial intelligence,inspection,routing,network topology,color,parallel algorithms,indexes,topology,indexation,parallel processing,sorting | Log-log plot,Edge coloring,Discrete mathematics,Binary logarithm,Combinatorics,Chromatic scale,Upper and lower bounds,Parallel algorithm,Parallel processing,Mathematics | Journal |
Volume | Issue | ISSN |
77 | 2 | Information and Computation |
ISBN | Citations | PageRank |
0-8186-0740-8 | 78 | 11.58 |
References | Authors | |
5 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernd Becker | 1 | 78 | 11.58 |
| Hans-Ulrich Simon | 2 | 567 | 104.52 |