The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks

Limei Lin, Shuming Zhou, Li Xu, Dajin Wang

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

Extra connectivity, diagnosability, and conditional diagnosability are all important measures for a multiprocessor system's ability to diagnose and tolerate faults. In this paper, we analyze the fault tolerance ability for the alternating group graph, a well-known interconnection network proposed for multiprocessor systems, establish the h-extra connectivity, where 1 ≤ h ≤ 3 , and prove that the conditional diagnosability of an n-dimensional alternating group graph, denoted by AGn, is 8n - 27 (n ≥ 4) under the PMC model. This is about four times of the AGn's traditional diagnosability. As a byproduct, the strong diagnosability of AGn is also obtained.

Original languageEnglish
Article number6879268
Pages (from-to)2352-2362
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume26
Issue number8
DOIs
StatePublished - 1 Aug 2015

Keywords

  • Alternating group graphs
  • PMC model
  • conditional diagnosability
  • extra connectivity
  • fault tolerance
  • strong diagnosability
  • system-level diagnosis

Fingerprint Dive into the research topics of 'The Extra Connectivity and Conditional Diagnosability of Alternating Group Networks'. Together they form a unique fingerprint.

Cite this