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.
|Journal||ACM Transactions on Design Automation of Electronic Systems|
|Publication status||Published - 2013 Mar 1|
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering