An Efficient Algorithm for Identifying the Most Likely Fault Set in a Probabilistically Diagnosable System
Dahbura · IEEE Transactions on Computers · 1986
An O(n3) algorithm is given for determining the most likely set of faulty processors in a class of systems introduced by Maheshwari and Hakimi[6], known as probabilistically diagnosable systems. The technique uses the a priori probability of failure of each unit combined with the results of tests which the processors administer to one another to perform diagnosis. The algorithm uses well-known results on network flow and minimum weight vertex cover sets.