## Abstract

(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= 2^{m-1} × (m ^{-3}) × lg(m^{-1}) (m^{-1})/(m^{-1}) ^{2} if 2^{m-2} ≤ n(G)<; m 2^{m-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.

Original language | English |
---|---|

Article number | 5601693 |

Pages (from-to) | 1704-1717 |

Number of pages | 14 |

Journal | IEEE Transactions on Computers |

Volume | 60 |

Issue number | 12 |

DOIs | |

Publication status | Published - 2011 Dec 1 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics