TY - JOUR
T1 - (t,k)-diagnosis for component-composition graphs under the MM* model
AU - Chen, Chun An
AU - Hsieh, Sun Yuan
PY - 2011
Y1 - 2011
N2 - (t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(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 (Ω(h),κ(G))-diagnosable, where h= 2m-1 × (m -3) × lg(m-1) (m-1)/(m-1) 2 if 2m-2 ≤ n(G)<; m 2m-1 × (m-3)/m-1 if n(G) ≥ m!. 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.
AB - (t, k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least t faulty processors be identified and replaced in each iteration provided there are at most t faulty processors, where t ≥ k. Let κ(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 (Ω(h),κ(G))-diagnosable, where h= 2m-1 × (m -3) × lg(m-1) (m-1)/(m-1) 2 if 2m-2 ≤ n(G)<; m 2m-1 × (m-3)/m-1 if n(G) ≥ m!. 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.
UR - http://www.scopus.com/inward/record.url?scp=84873465914&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873465914&partnerID=8YFLogxK
U2 - 10.1109/TC.2010.201
DO - 10.1109/TC.2010.201
M3 - Article
AN - SCOPUS:84873465914
VL - 60
SP - 1704
EP - 1717
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
SN - 0018-9340
IS - 12
M1 - 5601693
ER -