Sequential Diagnosability is Co-NP Complete

Vijay Raghavan, Anand Tripathi

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


The question of determining the sequential diagnosability number of system in the PMC model has remained open since it was first formulated two decades ago. We show that this problem is co-NP complete. The problem is also shown to be co-NP complete even when restricted to planar graphs both in the weighted and the BGM models.

Original languageEnglish (US)
Pages (from-to)584-595
Number of pages12
JournalIEEE Transactions on Computers
Issue number5
StatePublished - May 1991


Dive into the research topics of 'Sequential Diagnosability is Co-NP Complete'. Together they form a unique fingerprint.

Cite this