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 条

[31] Conditional Diagnosability of k-Ary n-Cubes under the PMC Model
Chang, Nai-Wen
Lin, Tzu-Yin
Hsieh, Sun-Yuan
ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2012, 17 (04)
[32] Conditional Diagnosability Algorithm for the Exchanged Hypercube under the PMC model
Gui, Weixia
Liang, Jiarong
Liu, Cui
PROCEEDINGS OF THE 3RD INTERNATIONAL CONFERENCE ON MECHATRONICS AND INDUSTRIAL INFORMATICS, 2015, 31 : 699 - 703
[33] Conditional Diagnosability of Matching Composition Networks Under the PMC Model
Xu, Min
Thulasiraman, Krishnaiyan
Hu, Xiao-Dong
IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS, 2009, 56 (11) : 875 - 879
[34] Conditional diagnosability algorithm for hypercube under the PMC model
Zhang, Liguo
Du, Huimin
Han, Jungang
Xi'an Dianzi Keji Daxue Xuebao/Journal of Xidian University, 2012, 39 (05): : 148 - 153
[35] The pessimistic diagnosability of alternating group graphs under the PMC model
Tsai, Chang-Hsiung
INFORMATION PROCESSING LETTERS, 2015, 115 (02) : 151 - 154
[36] The g-good-neighbor conditional diagnosability of the crossed cubes under the PMC and MM* model
Guo, Jia
Li, Desai
Lu, Mei
THEORETICAL COMPUTER SCIENCE, 2019, 755 : 81 - 88
[37] A Kind of Conditional Connectivity of Cayley Graphs Generated by 2-trees
Xu, Liqiong
Zhou, Shuming
Lian, Guanqin
Luo, Zuwen
COMPUTER JOURNAL, 2018, 61 (05) : 714 - 721
[38] Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees
Yang, Weihua
Li, Hengzhe
He, Wei-hua
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2015, 92 (07) : 1345 - 1352
[39] Component connectivity of Cayley graphs generated by transposition trees
Xu, Liqiong
Zhou, Shuming
Yang, Weihua
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, 2020, 35 (01) : 103 - 110
[40] The 1-good-neighbor connectivity and diagnosability of Cayley graphs generated by complete graphs
Wang, Mujiangshan
Lin, Yuqing
Wang, Shiying
DISCRETE APPLIED MATHEMATICS, 2018, 246 : 108 - 118

← 1 2 3 4 5 →