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

Chun An Chen, Sun-Yuan Hsieh

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


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
Issue number2
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