An Efficient Algorithm for Identifying the Most Likely Fault Set in a Probabilistically Diagnosable System
- 1 April 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (4) , 354-356
- https://doi.org/10.1109/tc.1986.1676769
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Fault-Tolerant Computing—Concepts and ExamplesIEEE Transactions on Computers, 1984
- An 0(n2.5) Fault Identification Algorithm for Diagnosable SystemsIEEE Transactions on Computers, 1984
- A fault diagnosis algorithm for asymmetric modular architecturesIEEE Transactions on Computers, 1981
- An O(|V|3) algorithm for finding maximum flows in networksInformation Processing Letters, 1978
- On Models for Diagnosable Systems and Probabilistic Fault DiagnosisIEEE Transactions on Computers, 1976
- Graph Theory with ApplicationsPublished by Springer Nature ,1976
- A diagnosing algorithm for networksInformation and Control, 1975
- Characterization of Connection Assignment of Diagnosable SystemsIEEE Transactions on Computers, 1974
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- On the Connection Assignment Problem of Diagnosable SystemsIEEE Transactions on Electronic Computers, 1967