T/t-diagnosability of regular graphs under the PMC model

Chun An Chen, Sun-Yuan Hsieh

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

A system is t/t-diagnosable if, given any collection of test results, the faulty nodes can be isolated to within a set of at most t nodes provided that the number of faulty nodes does not exceed t. Given an N-vertex graph G that is regular with the common degree d and has no cycle of three or four vertices, this study shows that G is (2d- 2)/(2d- 2)-diagnosable if N ≥ 4d- 3 > 0. Based on this result, the t/t-diagnosabilities of several classes of graphs can be computed efficiently.

Original languageEnglish
Article number20
JournalACM Transactions on Design Automation of Electronic Systems
Volume18
Issue number2
DOIs
Publication statusPublished - 2013 Mar 1

All Science Journal Classification (ASJC) codes

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

Cite this

@article{d860431ae0df435795d9db130e9d901c,
title = "T/t-diagnosability of regular graphs under the PMC model",
abstract = "A system is t/t-diagnosable if, given any collection of test results, the faulty nodes can be isolated to within a set of at most t nodes provided that the number of faulty nodes does not exceed t. Given an N-vertex graph G that is regular with the common degree d and has no cycle of three or four vertices, this study shows that G is (2d- 2)/(2d- 2)-diagnosable if N ≥ 4d- 3 > 0. Based on this result, the t/t-diagnosabilities of several classes of graphs can be computed efficiently.",
author = "Chen, {Chun An} and Sun-Yuan Hsieh",
year = "2013",
month = "3",
day = "1",
doi = "10.1145/2442087.2442091",
language = "English",
volume = "18",
journal = "ACM Transactions on Design Automation of Electronic Systems",
issn = "1084-4309",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

T/t-diagnosability of regular graphs under the PMC model. / Chen, Chun An; Hsieh, Sun-Yuan.

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

Research output: Contribution to journalArticle

TY - JOUR

T1 - T/t-diagnosability of regular graphs under the PMC model

AU - Chen, Chun An

AU - Hsieh, Sun-Yuan

PY - 2013/3/1

Y1 - 2013/3/1

N2 - A system is t/t-diagnosable if, given any collection of test results, the faulty nodes can be isolated to within a set of at most t nodes provided that the number of faulty nodes does not exceed t. Given an N-vertex graph G that is regular with the common degree d and has no cycle of three or four vertices, this study shows that G is (2d- 2)/(2d- 2)-diagnosable if N ≥ 4d- 3 > 0. Based on this result, the t/t-diagnosabilities of several classes of graphs can be computed efficiently.

AB - A system is t/t-diagnosable if, given any collection of test results, the faulty nodes can be isolated to within a set of at most t nodes provided that the number of faulty nodes does not exceed t. Given an N-vertex graph G that is regular with the common degree d and has no cycle of three or four vertices, this study shows that G is (2d- 2)/(2d- 2)-diagnosable if N ≥ 4d- 3 > 0. Based on this result, the t/t-diagnosabilities of several classes of graphs can be computed efficiently.

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

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

U2 - 10.1145/2442087.2442091

DO - 10.1145/2442087.2442091

M3 - Article

AN - SCOPUS:84878506651

VL - 18

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 -