Conditional diagnosability of cayley graphs generated by transposition trees under the PMC model

Naiwen Chang; Eddie Cheng; Sunyuan Hsieh

doi:10.1145/2699854

Conditional diagnosability of cayley graphs generated by transposition trees under the PMC model

Naiwen Chang, Eddie Cheng, Sunyuan Hsieh

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article › peer-review

20 Citations (Scopus)

Abstract

Processor fault diagnosis has played an essential role inmeasuring 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]).

Original language	English
Article number	20
Journal	ACM Transactions on Design Automation of Electronic Systems
Volume	20
Issue number	2
DOIs	https://doi.org/10.1145/2699854
Publication status	Published - 2015 Feb 1

All Science Journal Classification (ASJC) codes

Computer Science Applications
Computer Graphics and Computer-Aided Design
Electrical and Electronic Engineering

Access to Document

10.1145/2699854

Cite this

@article{11ffbc4722af41a7ac7be93acf1b75a0,

title = "Conditional diagnosability of cayley graphs generated by transposition trees under the PMC model",

abstract = "Processor fault diagnosis has played an essential role inmeasuring 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]).",

author = "Naiwen Chang and Eddie Cheng and Sunyuan Hsieh",

note = "Publisher Copyright: {\textcopyright} 2015 ACM.",

year = "2015",

month = feb,

day = "1",

doi = "10.1145/2699854",

language = "English",

volume = "20",

journal = "ACM Transactions on Design Automation of Electronic Systems",

issn = "1084-4309",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Conditional diagnosability of cayley graphs generated by transposition trees under the PMC model

AU - Chang, Naiwen

AU - Cheng, Eddie

AU - Hsieh, Sunyuan

PY - 2015/2/1

Y1 - 2015/2/1

N2 - Processor fault diagnosis has played an essential role inmeasuring 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]).

AB - Processor fault diagnosis has played an essential role inmeasuring 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]).

UR - http://www.scopus.com/inward/record.url?scp=84924085293&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84924085293&partnerID=8YFLogxK

U2 - 10.1145/2699854

DO - 10.1145/2699854

M3 - Article

AN - SCOPUS:84924085293

SN - 1084-4309

VL - 20

JO - ACM Transactions on Design Automation of Electronic Systems

JF - ACM Transactions on Design Automation of Electronic Systems

IS - 2

M1 - 20

ER -

Conditional diagnosability of cayley graphs generated by transposition trees under the PMC model

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this