Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model

被引：17
|
作者：
Chang, Naiwen [1 ]
Cheng, Eddie [2 ]
Hsieh, Sunyuan [1 ]
机构：
[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 70101, Taiwan
[2] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA
来源：
ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS | 2015年 / 20卷 / 02期
关键词：
Interconnection networks; PMCmodel; conditional diagnosability; Cayley graphs; fault tolerance; multiprocessor systems; Design; Algorithms; Performance; COMPOSITION NETWORKS; INTERCONNECTION NETWORKS; CONNECTION ASSIGNMENT; FAULT IDENTIFICATION; STAR GRAPHS; DIAGNOSIS;
D O I：
10.1145/2699854
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n -11 for n >= 4 except for the n-dimensional star graph for which it has been shown to be 8n-21 for n >= 5 (refer to Chang andHsieh [2014]).
引用
收藏
页数：16
相关论文
共 50 条
  • [21] 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
  • [22] Conditional Diagnosability of Augmented Cubes under the PMC Model
    Chang, Nai-Wen
    Hsieh, Sun-Yuan
    IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, 2012, 9 (01) : 46 - 60
  • [23] Conditional diagnosability of hypermesh optical multiprocessor systems under the PMC model
    Yang, Erjie
    Yang, Xiaofan
    Dong, Qiang
    Li, Jing
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2011, 88 (11) : 2275 - 2284
  • [24] The Extendability of Cayley Graphs Generated by Transposition Trees
    Feng, Yongde
    Xie, Yanting
    Liu, Fengxia
    Xu, Shoujun
    MATHEMATICS, 2022, 10 (09)
  • [25] Conditional diagnosability of multiprocessor systems based on complete-transposition graphs
    Xu, Liqiong
    Zhou, Shuming
    Lian, Guanqin
    DISCRETE APPLIED MATHEMATICS, 2018, 247 : 367 - 379
  • [26] Conditional Diagnosability of Burnt Pancake Networks Under the PMC Model
    Song, Sulin
    Zhou, Shuming
    Li, Xiaoyan
    COMPUTER JOURNAL, 2016, 59 (01) : 91 - 105
  • [27] On the Strictness of a Bound for the Diameter of Cayley Graphs Generated by Transposition Trees
    Ganesan, Ashwin
    MATHEMATICAL MODELLING AND SCIENTIFIC COMPUTATION, 2012, 283 : 54 - 61
  • [28] Conditional diagnosability of the SPn graphs under the comparison diagnosis model
    Guo, Jia
    Lu, Mei
    APPLIED MATHEMATICS AND COMPUTATION, 2018, 336 : 249 - 256
  • [29] Linearly many faults in Cayley graphs generated by transposition trees
    Cheng, Eddie
    Liptak, Laszlo
    INFORMATION SCIENCES, 2007, 177 (22) : 4877 - 4882
  • [30] The spanning cyclability of Cayley graphs generated by transposition trees
    Qiao, Hongwei
    Sabir, Eminjan
    Meng, Jixiang
    DISCRETE APPLIED MATHEMATICS, 2023, 328 : 60 - 69
12345