Title :
Lower bound for degree of sequential diagnosability of Cayley graphs
Author :
Yamada, Toshinori
Author_Institution :
Div. of Math., Electron. & Inf., Saitama Univ., Saitama, Japan
Abstract :
This paper presents that the degree of sequential diagnosability of an N-vertex Cayley graph is Ω(N/D) by generalizing a known technique of finding a lower bound for that of a CCC(cube-connected cycles), where D is the diameter of the Cayley graph. From the lower bound, it is shown that the degrees of sequential diagnosability of the N-vertex star graph and wrapped butterfly are Ω(N log log N/log N) and Ω(N/log N), respectively.
Keywords :
fault simulation; graph theory; integrated circuit design; microprocessor chips; multiprocessor interconnection networks; Cayley graphs; cube connected cycles; lower bound; sequential diagnosability; Circuit faults; Hypercubes; Integrated circuit modeling; Multiprocessing systems; Program processors; Sequential diagnosis; Testing;
Conference_Titel :
Symbolic and Numerical Methods, Modeling and Applications to Circuit Design (SM2ACD), 2010 XIth International Workshop on
Conference_Location :
Gammath
Print_ISBN :
978-1-4244-6816-4
DOI :
10.1109/SM2ACD.2010.5672318
