TY - JOUR
T1 - The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model
AU - Lin, Limei
AU - Hsieh, Sun Yuan
AU - Xu, Li
AU - Zhou, Shuming
AU - Chen, Riqing
N1 - Funding Information:
The authors would like to thank the anonymous referees for their critical review and valuable comments. This work was supported by the National Natural Science Foundation of China (No. 61572010 , No. 61702100 , No. 61702103 and No. 61771140 ), China Postdoctoral Science Foundation (No. 2017M612107 ), Foundation of Cloud Computing and Big Data for Agriculture and Forestry (Grant No. 117-612014063 ), Research Fund for the Doctoral Program of Higher Education of China (No. 20113219120019 ), Natural Science Foundation of Fujian Province (No. 2017J01738 ), Fujian Normal University Innovative Research Team (No. IRTL1207 ).
Publisher Copyright:
© 2017
PY - 2018/8
Y1 - 2018/8
N2 - Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. However, the extra connectivity and conditional diagnosability of many well-known networks have been independently investigated. Fault diagnosis of general regular graph is more meaningful than that of special graph. In this paper, the relationship between extra connectivity and conditional diagnosability of regular graphs is explored. First, we determine that the conditional diagnosability under the PMC model equals 3-extra connectivity plus 1 or 3-extra connectivity plus 2. Finally, we give empirical analysis on extra connectivity and conditional diagnosability of some graphs by our proposed relationship.
AB - Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. However, the extra connectivity and conditional diagnosability of many well-known networks have been independently investigated. Fault diagnosis of general regular graph is more meaningful than that of special graph. In this paper, the relationship between extra connectivity and conditional diagnosability of regular graphs is explored. First, we determine that the conditional diagnosability under the PMC model equals 3-extra connectivity plus 1 or 3-extra connectivity plus 2. Finally, we give empirical analysis on extra connectivity and conditional diagnosability of some graphs by our proposed relationship.
UR - http://www.scopus.com/inward/record.url?scp=85039049390&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85039049390&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2017.11.004
DO - 10.1016/j.jcss.2017.11.004
M3 - Article
AN - SCOPUS:85039049390
VL - 95
SP - 1
EP - 18
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
SN - 0022-0000
ER -