(t, k)-Diagnosis for Matching Composition Networks Under the MM* Model

Guey Yun Chang, Gen Huey Chen

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and repaired in each iteration provided there are at most t faulty processors, where t > k. In this paper, a (t, k)-diagnosis algorithm under the MM* model is proposed for matching composition networks, which include many well-known interconnection networks, such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that a matching composition network of n dimensions is (Ω(2*log n/n), n)-diagnosable.

Original languageEnglish
Pages (from-to)73-79
Number of pages7
JournalIEEE Transactions on Computers
Issue number1
StatePublished - 1 Jan 2007


  • (t, k)-diagnosis
  • Diagnosability
  • MM* model
  • matching composition network
  • multiprocessor system
  • precise diagnosis strategy


Dive into the research topics of '(t, k)-Diagnosis for Matching Composition Networks Under the MM* Model'. Together they form a unique fingerprint.

Cite this