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 条
  • [21] Conditional diagnosability of a class of matching composition networks under the comparison model
    Xu, Min
    Thulasiraman, Krishnaiyan
    Zhu, Qiang
    THEORETICAL COMPUTER SCIENCE, 2017, 674 : 43 - 52
  • [22] Conditional diagnosability of hypercubes under the comparison diagnosis model
    Hsu, Guo-Huang
    Chiang, Chieh-Feng
    Shih, Lun-Min
    Hsu, Lih-Hsing
    Tan, Jimmy J. M.
    JOURNAL OF SYSTEMS ARCHITECTURE, 2009, 55 (02) : 140 - 146
  • [23] Conditional diagnosability of component-composition graphs under the PMC model
    Lee, Chia-Wei
    THEORETICAL COMPUTER SCIENCE, 2020, 836 : 16 - 28
  • [24] Extra Conditional Diagnosability of Hypercubes under the Bounded PMC Model
    Tian, Yongcui
    Zhu, Qiang
    Lv, Chaofeng
    2022 ASIA CONFERENCE ON ALGORITHMS, COMPUTING AND MACHINE LEARNING (CACML 2022), 2022, : 391 - 396
  • [25] The 3-extra conditional diagnosability of balanced hypercubes under MM* model
    Li, Lili
    Zhang, Xing
    Zhu, Qiang
    Bai, Yiguang
    DISCRETE APPLIED MATHEMATICS, 2022, 309 : 310 - 316
  • [26] CONDITIONAL DIAGNOSABILITY OF CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES UNDER THE COMPARISON DIAGNOSIS MODEL
    Lin, Cheng-Kuan
    Tan, Jimmy J. M.
    Hsu, Lih-Hsing
    Cheng, Eddie
    Liptak, Laszlo
    JOURNAL OF INTERCONNECTION NETWORKS, 2008, 9 (1-2) : 83 - 97
  • [27] Relationship between extra edge connectivity and component edge connectivity for regular graphs
    Hao, Rong-Xia
    Gu, Mei-Mei
    Chang, Jou-Ming
    THEORETICAL COMPUTER SCIENCE, 2020, 833 : 41 - 55
  • [28] Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model
    Chang, Naiwen
    Cheng, Eddie
    Hsieh, Sunyuan
    ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2015, 20 (02)
  • [29] The extra connectivity, extra conditional diagnosability and t/k-diagnosability of the data center network DCell
    Li, Xiaoyan
    Fan, Jianxi
    Lin, Cheng-Kuan
    Cheng, Baolei
    Jia, Xiaohua
    THEORETICAL COMPUTER SCIENCE, 2019, 766 : 16 - 29
  • [30] Conditional diagnosability of Cayley graphs generated by wheel graphs under the PMC model
    Wei, Yulong
    Xu, Min
    THEORETICAL COMPUTER SCIENCE, 2021, 849 : 163 - 172
12345