Improved Diagnosability Algorithms

Vijay Raghavan, Anand R. Tripathi

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


We present improved one-step diagnosability algorithms for both the BGM and PMC models. Using the letters n, m, and r to denote the number of units, the number of tests, and the diagnosability number, respectively, the results of the paper can be summarized as follows: in the BGM model, our algorithm has a complexity of [formula Omitted] improving on Narasimhan and Nakajima’s O (nr3)algorithm; in the PMC model, our algorithm has a complexity of O(nr2.5) improving on Sullivan’s O(mn1.5) algorithm. Further, the ideas used in our algorithm for the PMC model can be easily extended to improve Sullivan’s algorithms for determining the t/t + k diagnosability numbers.

Original languageEnglish (US)
Pages (from-to)143-153
Number of pages11
JournalIEEE Transactions on Computers
Issue number2
StatePublished - Feb 1991


Dive into the research topics of 'Improved Diagnosability Algorithms'. Together they form a unique fingerprint.

Cite this