Component-composition graphs: (t,k)-diagnosability and its application

Chun An Chen, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


((t,k))-diagnosis, which is a generalization of sequential diagnosis, requires that at least (k) faulty processors should be identified and repaired in each iteration provided there are at most (t) faulty processors, where (t\ge k). In this paper, we propose a unified approach for computing the ((t,k))-diagnosability of numerous multiprocessor systems (graphs) under the Preparata, Metze, and Chien's model, including hypercubes, crossed cubes, twisted cubes, locally twisted cubes, multiply-twisted cubes, generalized twisted cubes, recursive circulants, Möbius cubes, Mcubes, star graphs, bubble-sort graphs, pancake graphs, and burnt pancake graphs. Our approach first sketches the common properties of the above classes of graphs, and defines a superclass of graphs, called (m)-dimensional component-composition graphs, to cover them. We then show that the (m)-dimensional component-composition graph (G) for (m ≥ 4) is ((Ω (h),κ (G)))-diagnosable, where h= and (κ (G)) and (V(G)) denote the node connectivity and the number of nodes in (G), respectively. Based on this result, the ((t,k))-diagnosability of the above multiprocessor systems can be computed efficiently.

Original languageEnglish
Article number6165261
Pages (from-to)1097-1110
Number of pages14
JournalIEEE Transactions on Computers
Issue number6
Publication statusPublished - 2013 May 13

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Component-composition graphs: (t,k)-diagnosability and its application'. Together they form a unique fingerprint.

Cite this