The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model

Limei Lin, Sun Yuan Hsieh, Li Xu, Shuming Zhou, Riqing Chen

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)

Abstract

Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. However, the extra connectivity and conditional diagnosability of many well-known networks have been independently investigated. Fault diagnosis of general regular graph is more meaningful than that of special graph. In this paper, the relationship between extra connectivity and conditional diagnosability of regular graphs is explored. First, we determine that the conditional diagnosability under the PMC model equals 3-extra connectivity plus 1 or 3-extra connectivity plus 2. Finally, we give empirical analysis on extra connectivity and conditional diagnosability of some graphs by our proposed relationship.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalJournal of Computer and System Sciences
Volume95
DOIs
Publication statusPublished - 2018 Aug

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model'. Together they form a unique fingerprint.

Cite this