@article{Liu2024, 
author = {Xiao-Qing Liu and Shu-Ming Zhou and Eddie Cheng and Hong Zhang},
title = {The t/s-Diagnosability and Diagnostic Strategy of Balanced Hypercube Under Two Classic Diagnostic Models},
year = {2024},
journal = {Journal of Computer Science and Technology},
volume = {39},
number = {5},
pages = {1207-1222},
keywords = {fault diagnosis, t/s-diagnosability, t/s-diagnosis algorithm, balanced hypercube},
url = {https://www.sciopen.com/article/10.1007/s11390-024-2732-5},
doi = {10.1007/s11390-024-2732-5},
abstract = {Fault diagnosis plays a crucial role in the fault tolerability assessment of an interconnection network, which is of great value in the design and maintenance of large-scale multiprocessor systems. A  t/s-diagnostic strategy, as the generalization of the  t/t-diagnostic strategy, refers to the self-diagnosis of a multiprocessor system in which all faulty vertices can be identified in a set of size at most  s in the presence of at most  t faulty vertices. In this work, we show that the balanced hypercube  BHn(n⩾4) is  ((2n+1)⌈g/2⌉−⌈g/2⌉2)/((2n+1)⌈g/2⌉−⌈g/2⌉2+(g−2))-diagnosable under both the Preparata, Metze, and Chien (PMC) and MM* models for  4⩽⌈g/2⌉⩽n. Moreover, we propose two effective  t/s-diagnosis algorithms under the PMC and MM* models with time complexity  O(NlogN) and  O(N(logN)2) ( N=22n is the order of  BHn), respectively. Finally, comparison results indicate that  t/s-diagnosability strengthens the self-diagnosable capability of the system compared with traditional diagnosabilities.}
}