Diagnosability of arrangement graphs with missing edges under the MM* model

被引：2

作者：

Wang, Shiying ^{[1
]}

Ma, Xiaolei ^{[1
]}

机构：

[1] Henan Normal Univ, Coll Math & Informat Sci, Xinxiang 453007, Henan, Peoples R China

来源：

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS | 2020年 / 35卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Interconnection network; Local diagnosability; MM* model; arrangement graph; LOCAL DIAGNOSABILITY; DIAGNOSIS;

D O I：

10.1080/17445760.2019.1600688

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Diagnosability is an important parameter to measure the fault tolerance of interconnection networks. Arrangement graph is a generalisation of the star graphs A(n,k) yet it is more flexible in its size than the star graphs. In this paper, we study the local diagnosability of A(n,k) and show that it has the strong local diagnosability property even if there exist (k - 1) (n - k) - 1 missing edges in it under the MM* model, and the result is optimal with respect to the number of missing edges. [GRPAHICS]

引用

页码：69 / 80

页数：12

共 17 条

[1] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[2]

Bondy J. A., 2008, GTM

[3] Linearly many faults in arrangement graphs [J].

Cheng, Eddie ;

Liptak, Laszlo ;

Yuan, Allen .

NETWORKS, 2013, 61 (04) :281-289

[4] Diagnosability of Cayley graphs generated by transposition trees with missing edges [J].

Cheng, Eddie ;

Liptak, Laszlo .

INFORMATION SCIENCES, 2013, 238 :250-252

[5] Strong local diagnosability of (n, k)-star graphs and Cayley graphs generated by 2-trees with missing edges [J].

Cheng, Eddie ;

Liptak, Laszlo ;

Steffy, Daniel E. .

INFORMATION PROCESSING LETTERS, 2013, 113 (12) :452-456

[6] Diagnosability of star graphs with missing edges [J].

Chiang, Chieh-Feng ;

Hsu, Guo-Huang ;

Shih, Lun-Min ;

Tan, Jimmy J. M. .

INFORMATION SCIENCES, 2012, 188 :253-259

[7] Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model [J].

Chiang, Chieh-Feng ;

Tan, Jimmy J. M. .

IEEE TRANSACTIONS ON COMPUTERS, 2009, 58 (02) :251-259

[8] On the arrangement graph [J].

Chiang, WK ;

Chen, RJ .

INFORMATION PROCESSING LETTERS, 1998, 66 (04) :215-219

[9] ARRANGEMENT GRAPHS - A CLASS OF GENERALIZED STAR GRAPHS [J].

DAY, K ;

TRIPATHI, A .

INFORMATION PROCESSING LETTERS, 1992, 42 (05) :235-241

[10] A local diagnosability measure for multiprocessor systems [J].

Hsu, Guo-Huang ;

Tan, Jimmy J. M. .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2007, 18 (05) :598-607

← 1 2 →