The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model

被引：40

作者：

Lin, Limei ^{[1
,3
]}

Hsieh, Sun-Yuan ^{[4
]}

Xu, Li ^{[2
,3
]}

Zhou, Shuming ^{[2
,3
]}

Chen, Riqing ^{[1
]}

机构：

[1] Fujian Agr & Forestry Univ, Fac Comp Sci & Informat Technol, Fuzhou 350002, Fujian, Peoples R China

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

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

[4] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 701, Taiwan

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2018年 / 95卷

基金：

中国博士后科学基金; 高等学校博士学科点专项科研基金; 中国国家自然科学基金;

关键词：

Regular graphs; Reliability; Extra connectivity; Conditional diagnosability; PMC model; MULTIPROCESSOR SYSTEMS; RELIABILITY EVALUATION; DIAGNOSIS; NETWORKS; EXTRACONNECTIVITY; HYPERCUBES;

D O I：

10.1016/j.jcss.2017.11.004

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (C) 2017 Published by Elsevier Inc.

引用

页码：1 / 18

页数：18

共 43 条

[1]

[Anonymous], 1992, RELIABILITY EVALUATI

[2] Complex networks: Structure and dynamics [J].