Journal
THEORETICAL COMPUTER SCIENCE
Volume 421, Issue -, Pages 62-69Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2011.11.016
Keywords
Distributed systems; Interconnection networks; Node failure; Link failure; Bubble-sort graphs
Categories
Funding
- National Natural Science Foundation of China [61070229]
- Natural Science Foundation for Young Scientists of Shanxi Province, China [2011021004]
Ask authors/readers for more resources
The bubble-sort graph B-n is one of the attractive underlying topologies for distributed systems. F-B(n, k) (resp. f(B)(n, k)) is the minimum number of faulty nodes (resp. links) that make every (n - k)-dimensional sub-bubble-sort graph faulty in B, under node (resp. link) failure model. In this paper, we proved that F-B(n, 0) = f(B)(n, 0) = 1, F-B(n, 1) = f(B)(n, 1) = n for n >= 4, F-B(n, 2) <= f(B)(n, 2) <= n(2n - 3) for n >= 6, F-B(n, n - 2) = n!/2 for n >= 3, f(B)(n, n - 2) = (n - 1)n!/2 for n >= 3, F-B(n, n - 1) = n! for n >= 2, and F-B(n, k) <= f(B)(n, k) <= inverted right perpendicular(k+ 1)/2inverted left perpendiculark!C-k(n) for n >= 6 and 3 <= k <= n - 3. (C) 2011 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available