合成圖的(t, k)-偵錯度與其應用

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and replaced in each iteration provided there are at most t faulty processors, where t>=k. In this paper, we propose a unified approach to compute the (t,k)-diagnosability for numerous 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. The key concept of our approach is to sketch the common graph properties of the above multiprocessor systems and demonstrate that their underlying topologies have a common super class of graphs, called component-composition graphs. We then show that the m-dimensional component-composition graph G for m>=4 is a lower bound of the (t,k)-diagnosability. Based on this result, the (t,k)-diagnosability of the referred multiprocessor systems can be e±ciently computed.