(t, k)-diagnosis for matching composition networks

Guey Yun Chang, Gen Huey Chen, Gerard J. Chang

Research output: Contribution to journalReview articlepeer-review

43 Scopus citations


(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. This paper proposes a (t, k)-diagnosis algorithm for matching composition networks, which include many well-known interconnection networks such as hypercubes, crossed cubes, twisted cubes, and Möbius cubes. It is shown that matching composition networks of n dimensions are (Ω(2log n/n),n)-diagnosable, where n > 5.

Original languageEnglish
Pages (from-to)88-92
Number of pages5
JournalIEEE Transactions on Computers
Issue number1
StatePublished - Jan 2006


  • (t, k)-diagnosis
  • Diagnosability
  • Matching composition network
  • Multiprocessor system
  • PMC model
  • Precise diagnosis strategy
  • Sequential diagnosis


Dive into the research topics of '(t, k)-diagnosis for matching composition networks'. Together they form a unique fingerprint.

Cite this