CONDITIONAL DIAGNOSABILITY OF CAYLEY GRAPHS GENERATED BY TRANSPOSITION TREES UNDER THE COMPARISON DIAGNOSIS MODEL

被引:92
作者
Lin, Cheng-Kuan [1 ]
Tan, Jimmy J. M. [1 ]
Hsu, Lih-Hsing [2 ]
Cheng, Eddie [3 ]
Liptak, Laszlo [3 ]
机构
[1] Natl Chiao Tung Univ, Dept Comp Sci, Hsinchu 30010, Taiwan
[2] Providence Univ, Dept Comp Sci & Informat Engn, Taichung 43301, Taiwan
[3] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA
关键词
Comparison diagnosis model; t-diagnosable; diagnosability; conditional diagnosability; star graph; Cayley graph;
D O I
10.1142/S0219265908002175
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The diagnosis of faulty processors plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Zheng et al. showed that the diagnosability of the n-dimensional star graph S-n is n - 1. Lai et al. introduced a restricted diagnosability of multiprocessor systems called conditional diagnosability. They consider the situation when no faulty set can contain all the neighbors of any vertex in the system. In this paper, we study the conditional diagnosability of Cayley graphs generated by transposition trees (which include the star graphs) under the comparison model, and show that it is 3n - 8 for n >= 4, except for the n-dimensional star graph, for which it is 3n - 7. Hence the conditional diagnosability of these graphs is about three times larger than their classical diagnosability.
引用
收藏
页码:83 / 97
页数:15
相关论文
共 40 条
[1]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[2]   Hyper hamiltonian laceability of Cayley graphs generated by transpositions [J].
Araki, Toru .
NETWORKS, 2006, 48 (03) :121-124
[3]   Embedding an arbitrary binary tree into the star graph [J].
Bagherzadeh, N ;
Dowd, M ;
Nassif, N .
IEEE TRANSACTIONS ON COMPUTERS, 1996, 45 (04) :475-481
[4]  
Bondy J. A., 1980, GRAPH THEORY APPL
[5]   Embedding complete binary trees into star and pancake graphs [J].
Bouabdallah, A ;
Heydemann, MC ;
Opatrny, J ;
Sotteau, D .
THEORY OF COMPUTING SYSTEMS, 1998, 31 (03) :279-305
[6]  
Cheng E., INT J FDN COMPUTER S
[7]  
Cheng E., 2006, C NUMER, V180, P81
[8]  
Cheng E., INFORM SCI
[9]  
DAHBURA AT, 1984, IEEE T COMPUT, V33, P486, DOI 10.1109/TC.1984.1676472
[10]  
Fan J, 2002, IEEE T PARALL DISTR, V13, P1084