Conditional $(t,k)$ -Diagnosis in Regular and Irregular Graphs Under the Comparison Diagnosis Model
Chia-Chen Wei, Chun-An Chen, Sun‐Yuan Hsieh · IEEE Transactions on Dependable and Secure Computing · 2016
Assume that there are at most t faulty vertices. A system is conditionally (t, k)-diagnosable if at least k faulty vertices (or all faulty vertices if fewer than k faulty vertices remain) can be identified in each iteration under the assumption that every vertex is adjacent to at least one fault-free vertex. Let κc(G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let Δ(G) be the maximum degrees of the given graph G. When a graph G satisfies the condition that for any pair of vertices with distance two has at least two common neighbors in G, we show the following two results: 1) An r-regular network G containing N vertices is conditionally (r+1/n+√(r+1)(r-1)/4x(G)N)2, kc(G)) diagnosable, where r ≥ 3 and N ≥ 4x(G)/(r+1)(25r-9). 2) An irregular network G containing N vertices is conditionally (Δ(G)+1/N-1, kc(G))-diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t, k)-diagnosabilities for augmented cubes, folded hypercubes, balanced hypercubes, and exchanged hypercubes.