This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from one component to the other one. The basic problem of diagnosis is known to be polynomial and NP-complete in the cases of single faults and multiple faults, respectively. We extend the complexity analysis to the case of faulty alarms, and also consider the problem of limiting the propagation of faults. We show that none of the considered diagnosis problems can be simplified by preprocessing the graph. (c) 2005 Wiley Periodicals, Inc.

Complexity and compilability of diagnosis and recovery of graph-based systems / Liberatore, Paolo. - In: INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS. - ISSN 0884-8173. - STAMPA. - 20:10(2005), pp. 1053-1076. [10.1002/int.20106]

Complexity and compilability of diagnosis and recovery of graph-based systems

LIBERATORE, Paolo
2005

Abstract

This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from one component to the other one. The basic problem of diagnosis is known to be polynomial and NP-complete in the cases of single faults and multiple faults, respectively. We extend the complexity analysis to the case of faulty alarms, and also consider the problem of limiting the propagation of faults. We show that none of the considered diagnosis problems can be simplified by preprocessing the graph. (c) 2005 Wiley Periodicals, Inc.
automated diagnosis; computational complexity; preprocessing
01 Pubblicazione su rivista::01a Articolo in rivista
Complexity and compilability of diagnosis and recovery of graph-based systems / Liberatore, Paolo. - In: INTERNATIONAL JOURNAL OF INTELLIGENT SYSTEMS. - ISSN 0884-8173. - STAMPA. - 20:10(2005), pp. 1053-1076. [10.1002/int.20106]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/124764
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact