The extra connectivity and extra diagnosability of regular interconnection networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

14 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)88-102
Journal / PublicationTheoretical Computer Science
Volume809
Online published31 Dec 2019
Publication statusPublished - 24 Feb 2020

Abstract

Reliability assessment of interconnection networks is critical to the design of multiprocessor systems. Extra connectivity and extra diagnosability are two important metric parameters for the reliability evaluation of interconnection networks. In this paper, we first establish that the i-extra connectivities of regular networks with some conditions Gn are (+ 1)− 2i for = 1, 2, where n ≥ 4, and then determine that the i-extra diagnosabilities of the networks under the PMC model and the MM* model are (+ 1)i for i = 1, 2, where n ≥ 4. Furthermore, two polynomial time diagnostic algorithms of regular interconnection networks under the PMC and MM* model are described. Finally, the corresponding extra connectivities and extra diagnosabilities of some networks, including the star networks, the pancake networks and the burnt pancake networks, can be derived by our results.

Research Area(s)

  • Extra connectivity, Extra diagnosability, Interconnection networks, MM* model, PMC model

Citation Format(s)

The extra connectivity and extra diagnosability of regular interconnection networks. / Lv, Mengjie; Fan, Jianxi; Zhou, Jingya et al.
In: Theoretical Computer Science, Vol. 809, 24.02.2020, p. 88-102.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review