Reliability assessment for modified bubble-sort networks.

In large-scale multiprocessor systems, it is significant to estimate the reliability of the interconnection networks. The κ k and λ k are two generalized measurements of reliability for networks. The κ k (λ k) of G is the minimum cardinality of a set of vertices (edges) of G , if any, whose deletion disconnects G , and every remaining component has minimum degree at least k. For the modified bubble-sort networks M B n , this paper proves κ k (M B n) = λ k (M B n) = 2 k (n − k) for k ≤ n / 2. The conclusions extend some known results in the literature, imply that to make a modified bubble-sort network M B n disconnected with all remaining vertices have at least k neighbors, at least 2 k (n − k) vertices or edges have to be faulty. [ABSTRACT FROM AUTHOR]