Sequential Diagnosability is Co-NP Complete

Vijay Raghavan, Anand Tripathi

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

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
Volume40
Issue number5
DOIs
StatePublished - May 1991

Bibliographical note

Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

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

Cite this