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.