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

Naiwen Chang, Eddie Cheng, Sun-Yuan Hsieh

Research output: Contribution to journalArticle

12 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 languageEnglish
Article number20
JournalACM Transactions on Design Automation of Electronic Systems
Volume20
Issue number2
DOIs
Publication statusPublished - 2015 Feb 1

Fingerprint

Stars
Failure analysis
Structural properties

All Science Journal Classification (ASJC) codes

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

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 Sun-Yuan Hsieh",
year = "2015",
month = "2",
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",

}

Conditional diagnosability of cayley graphs generated by transposition trees under the PMC model. / Chang, Naiwen; Cheng, Eddie; Hsieh, Sun-Yuan.

In: ACM Transactions on Design Automation of Electronic Systems, Vol. 20, No. 2, 20, 01.02.2015.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Chang, Naiwen

AU - Cheng, Eddie

AU - Hsieh, Sun-Yuan

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

VL - 20

JO - ACM Transactions on Design Automation of Electronic Systems

JF - ACM Transactions on Design Automation of Electronic Systems

SN - 1084-4309

IS - 2

M1 - 20

ER -