| |
[摘要]：(t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t >= k. Let kappa(G) and n(G) be, respectively, the node connectivity and the number of nodes in a graph G. In this paper, we compute the (t, k)-diagnosability for a class of component-composition graphs under the comparison diagnosis model. We show that the m-dimensional component-composition graph G (m >= 4) is (Omega(h), kappa(G))-diagnosable, whereh={2(m 2) x (m-3) x 1g (m-1)/(m-1)(2) if 2(m-1) <= n(G) < ml 2(m-2) x (m-3)/m-1 if n(G) >= ml.Based on this result, the (t, k)-diagnosability of several multiprocessor systems, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply twisted cubes, generalized twisted cubes, recursive circulants, Mobius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs, can be computed efficiently. |
|
