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 条

[41] Fault diagnosability of DQcube under the PMC model
Lv, Mengjie
Zhou, Shuming
Liu, Jiafei
Sun, Xueli
Lian, Guanqin
DISCRETE APPLIED MATHEMATICS, 2019, 259 : 180 - 192
[42] Strong diagnosability and conditional diagnosability of optical multi-mesh hypercube networks under the PMC model
Li, Xianyong
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2016, 93 (12) : 2054 - 2063
[43] Conditional diagnosability of hypermeshes under the comparison model
Yang, Erjie
Yang, Xiaofan
Dong, Qiang
Li, Jing
INFORMATION PROCESSING LETTERS, 2011, 111 (04) : 188 - 193
[44] A novel conditional diagnosability algorithm under the PMC model
郭晨
Liang Jiarong
Leng Ming
Peng Shuo
High Technology Letters, 2017, 23 (04) : 384 - 389
[45] Strong local diagnosability of (n, k)-star graphs and Cayley graphs generated by 2-trees with missing edges
Cheng, Eddie
Liptak, Laszlo
Steffy, Daniel E.
INFORMATION PROCESSING LETTERS, 2013, 113 (12) : 452 - 456
[46] Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper-stars
Cheng, Eddie
Hu, Philip
Jia, Roger
Liptak, Laszlo
NETWORKS, 2012, 59 (04) : 357 - 364
[47] The Cyclic Diagnosability Of Hypercubes Under The PMC Model And The MM* Model
Zhang, Hong
Zhou, Shuming
Cheng, Eddie
COMPUTER JOURNAL, 2024, 67 (02) : 709 - 718
[48] Conditional diagnosability and strong diagnosability of shuffle-cubes under the comparison model
Lin, Limei
Xu, Li
Zhou, Shuming
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2015, 92 (02) : 230 - 249
[49] FAULT-TOLERANT MAXIMAL LOCAL-CONNECTIVITY ON CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES
Shih, Lun-Min
Chiang, Chieh-Feng
Hsu, Lih-Hsing
Tan, Jimmy J. M.
JOURNAL OF INTERCONNECTION NETWORKS, 2009, 10 (03) : 253 - 260
[50] Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees
Li, Hengzhe
Yang, Weihua
Meng, Jixiang
DISCRETE MATHEMATICS, 2012, 312 (21) : 3087 - 3095

← 1 2 3 4 5 →