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
相关论文
共 50 条
  • [1] The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model
    Lin, Limei
    Hsieh, Sun-Yuan
    Xu, Li
    Zhou, Shuming
    Chen, Riqing
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2018, 95 : 1 - 18
  • [2] A new proof for exact relationship between extra connectivity and extra diagnosability of regular connected graphs under MM* model
    Huang, Yanze
    Lin, Limei
    Xu, Li
    THEORETICAL COMPUTER SCIENCE, 2020, 828 : 70 - 80
  • [3] Relationship between conditional diagnosability and 2-extra connectivity of symmetric graphs
    Hao, Rong-Xia
    Tian, Zeng-Xian
    Xu, Jun-Ming
    THEORETICAL COMPUTER SCIENCE, 2016, 627 : 36 - 53
  • [4] The extra connectivity and extra diagnosability of regular interconnection networks
    Lv, Mengjie
    Fan, Jianxi
    Zhou, Jingya
    Cheng, Baolei
    Jia, Xiaohua
    THEORETICAL COMPUTER SCIENCE, 2020, 809 : 88 - 102
  • [5] The Extra Connectivity, Extra Conditional Diagnosability, and t/m-Diagnosability of Arrangement Graphs
    Xu, Li
    Lin, Limei
    Zhou, Shuming
    Hsieh, Sun-Yuan
    IEEE TRANSACTIONS ON RELIABILITY, 2016, 65 (03) : 1248 - 1262
  • [6] The Extra, Restricted Connectivity and Conditional Diagnosability of Split-Star Networks
    Lin, Limei
    Xu, Li
    Zhou, Shuming
    Hsieh, Sun-Yuan
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2016, 27 (02) : 533 - 545
  • [7] Conditional diagnosability of the SPn graphs under the comparison diagnosis model
    Guo, Jia
    Lu, Mei
    APPLIED MATHEMATICS AND COMPUTATION, 2018, 336 : 249 - 256
  • [8] Conditional diagnosability of DCCLC graphs under the comparison model
    Yang, Erjie
    Yang, Xiaofan
    Dong, Qiang
    INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, 2011, 26 (03) : 239 - 248
  • [9] The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks
    Lin, Limei
    Zhou, Shuming
    Xu, Li
    Wang, Dajin
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (08) : 2352 - 2362
  • [10] The g-Extra Conditional Diagnosability of Graphs in Terms of g-Extra Connectivity
    Liu, Aixia
    Yuan, Jun
    Wang, Shiying
    PARALLEL PROCESSING LETTERS, 2020, 30 (03)
12345