Name
Abstract | ||
|---|---|---|
The complexity of the single-fault (SF) set diagnosability and SF-diagnosis problems under the symmetric invalidation models is discussed. It is shown that the SF-diagnosis problem under both these models is co-NP-complete and the SF-diagnosability problem is also co-NP-complete under the asymmetric invalidation model. The SF-diagnosability problem is also studied under the symmetric-invalidation model and a polynomial time-complexity algorithm is presented. These results are in contrast with the corresponding t-diagnosability and t-diagnosis problems, which are known to have polynomial time-complexity algorithms. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1109/12.16496 | IEEE Trans. Computers |
Keywords | Field | DocType |
computational complexity,fault tolerant computing,complexity,diagnosis problems,polynomial time-complexity algorithm,single fault set diagnosability,symmetric invalidation models,t-diagnosability | Polynomial,Computer science,Parallel computing,Multiprocessing,Theoretical computer science,Computational complexity theory | Journal |
Volume | Issue | ISSN |
38 | 2 | 0018-9340 |
Citations | PageRank | References |
7 | 1.26 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arun K. Somani | 1 | 2041 | 216.71 |
| V. K. Agarwal | 2 | 360 | 44.82 |
| D. Avis | 3 | 68 | 5.87 |