COMPUTATIONAL-COMPLEXITY ISSUES IN OPERATIVE DIAGNOSIS OF GRAPH-BASEDSYSTEMS

Systems that can be modeled as graphs, such thal nodes represent the c omponents and the edges represent the fault propagation between the co mponents, are considered. Some components are equipped with alarms tha t ring in response to faulty conditions. In these systems, two types o f problems are studied: a) fault diagnosis, and b) alarm placement. Th e fault diagnosis problems deal with computing the set of all potentia l failure sources that correspond to a set of ringing alarms A(R). Fir st, the single faults, where exactly one component can become faulty a t 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 diagn osis. The problem of detecting multiple faults is shown to be NP-compl ete. An alarm placement problem, that requires a single fault to be un iquely diagnosed, is examined; various versions of this problem are sh own to be NP-complete. The single fault diagnosis algorithms have been implemented and tested.