## Abstract

PMC model is the test-based diagnosis which a vertex performs the diagnosis by testing the neighbor vertices via the edges between them. If we only care about the status of a particular vertex, instead of doing global diagnosis, Hsu and Tan introduced the concept of local diagnosis and proposed two structures to diagnose a vertex. The local diagnosability of a vertex is upper bounded by its degree in the system. If the local diagnosability of a vertex is equal to its degree then we say it is locally optimal diagnosable. Usually, there is a gap between the local diagnosability and the lower bound guaranteed by the two structures mentioned above. Herein, we propose a new testing structure and corresponding diagnosis algorithm to diagnose a vertex under PMC model to better evaluate the local diagnosability. And this diagnosis algorithm takes linear time. Based on this new structure, we give a sufficient condition for a vertex to be locally optimal diagnosable. As its applications, we consider the sufficient and necessary condition for a vertex of hypercubes (resp. folded hypercubes) with faulty edges to be locally optimal diagnosable.

Original language | English |
---|---|

Pages (from-to) | 81-90 |

Number of pages | 10 |

Journal | Theoretical Computer Science |

Volume | 934 |

DOIs | |

State | Published - 23 Oct 2022 |

## Keywords

- Diagnosability
- Folded hypercube
- Hypercube
- Local diagnosability
- PMC model