Computational Complexity Issues in Operative Diagnosis of Graph-Based Systems

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

Abstract

Systems that can be modeled as graphs, such that nodes represent the components and the edges represent the fault propagation between the components, are considered. Some components are equipped with alarms that ring in response to faulty conditions. In these systems, two types of problems are studied: a) fault diagnosis, and b) alarm placement. The fault diagnosis problems deal with computing the set of all potential failure sources that correspond to a set of ringing alarms ar. first, the single faults, where exactly one component can become faulty at any time, are considered. Systems are classified into zero-time and nonzero-time systems based on fault propagation times, and the latter is further classified based on the knowledge of propagation times. For each of these classes algorithms are presented for single fault diagnosis. The problem of detecting multiple faults is shown to be NP-complete. An alarm placement problem, that requires a single fault to be uniquely diagnosed, is examined; various versions of this problem are shown to be NP-complete. The single fault diagnosis algorithms have been implemented and tested.

Original languageEnglish
Pages (from-to)447-457
Number of pages11
JournalIEEE Transactions on Computers
Volume42
Issue number4
DOIs
StatePublished - Apr 1993

Funding

Manuscript received March 22, 1991; revised March 6, 1992. This work was supported in part by the National Science Foundation under Grant IRI-918610. The author is with the Intelligent Systems Section, Oak Ridge National Laboratory, Oak Ridge, TN 37831-6364. IEEE Log Number 9207199.

Keywords

  • Alarm placement problems
  • NP-complete problems
  • algorithms and complexity
  • fault diagnosis
  • operative diagnosis
  • single and multiple faults

Fingerprint

Dive into the research topics of 'Computational Complexity Issues in Operative Diagnosis of Graph-Based Systems'. Together they form a unique fingerprint.

Cite this