## 摘要

(t,k)-Diagnosis, which is a generalization of sequential diagnosis, requires that at least k faulty processors be identified and repaired in each iteration when there are at most t faulty processors, where t ≥ k. Based on the assumption that each vertex is adjacent to at least one fault-free vertex, the conditional (t,k)-diagnosis of graphs was investigated by using the comparison diagnosis model. Lower bounds on the conditional (t, k)-diagnosability of graphs were derived, and applied to obtain the following results. 1) Symmetric d-dimensional grids are conditionally (N/2d+1 - 1,2d - 1)-diagnosable when d ≥ 2 and N (the number of vertices)≥ 4^{d}. 2) Symmetric d-dimensional tori are conditionally (1/5(N + min{8/5 N2/3, 2N-20/15} - 2),6)-diagnosable when d = 2 and N ≥ 49 and (N/2d+1 - 1,4d - 2)-diagnosable when d ≥ 3 and N ≥ 4^{d}. 3) Cube-connected cycles are conditionally (N/4 - 1, 4)-diagnosable. 4) k-ary trees are conditionally (N/k+1 - 1, 1)-diagnosable.

原文 | English |
---|---|

文章編號 | 6871331 |

頁（從 - 到） | 1622-1632 |

頁數 | 11 |

期刊 | IEEE Transactions on Computers |

卷 | 64 |

發行號 | 6 |

DOIs | |

出版狀態 | Published - 2015 六月 1 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics