Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model

被引：29

作者：

Lin, Limei ^{[1
,2
]}

Xu, Li ^{[1
,2
]}

Zhou, Shuming ^{[1
,2
]}

机构：

[1] Fujian Normal Univ, Sch Math & Comp Sci, Fuzhou 350007, Fujian, Peoples R China

[2] Fujian Normal Univ, Key Lab Network Secur & Cryptol, Fuzhou 350108, Fujian, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2016年 / 618卷

基金：

中国国家自然科学基金;

关键词：

Regular graphs; Reliability; Extra connectivity; Conditional diagnosability; Comparison model; FAULT DIAGNOSABILITY; CROSSED CUBES; DIAGNOSIS; EXTRACONNECTIVITY;

D O I：

10.1016/j.tcs.2015.12.031

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. The extra connectivity and the conditional diagnosability of many well-known multiprocessor systems have been widely investigated. In this paper, the relationship between the extra connectivity and the conditional diagnosability of regular graphs is explored. We establish that the conditional diagnosability under the comparison model is equal to the 2-extra connectivity. Finally, we give empirical analysis on the extra connectivity and conditional diagnosability of some graphs by our proposed relationship. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：21 / 29

页数：9

共 37 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].