A Polynomial Time Algorithm For Fault Diagnosability

1 January 1984

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

No. 02725428,p. 148-156
https://doi.org/10.1109/sfcs.1984.715911

Abstract

We present the first polynomial time algorithm for testing t-diagnosability. This is a significant advance in system level fault diagnosis. We also presented part of our analysis of t/s-diagnosability, including the fact that it is co-NP-complete and that there are polynomial algorithms for t/t and t/(t+1)-diagnosability.

Keywords

This publication has 20 references indexed in Scilit:

On Adaptive System Diagnosis
IEEE Transactions on Computers, 1984
A Fault-Tolerant Communication Architecture for Distributed Systems
IEEE Transactions on Computers, 1982
Fault Diagnosis in a Boolean n Cube Array of Microprocessors
IEEE Transactions on Computers, 1981
On Fault Identification in Diagnosable Systems
IEEE Transactions on Computers, 1981
A new method to test system diagnosability
Information Sciences, 1980
System-Level Fault Diagnosis
Computer, 1980
A Theory of Diagnosability of Digital Systems
IEEE Transactions on Computers, 1976
Network Flow and Testing Graph Connectivity
SIAM Journal on Computing, 1975
Characterization of Connection Assignment of Diagnosable Systems
IEEE Transactions on Computers, 1974
On the Connection Assignment Problem of Diagnosable Systems
IEEE Transactions on Electronic Computers, 1967

Cited by 45 articles