The extra connectivity and extra diagnosability of regular interconnection networks
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 88-102 |
Journal / Publication | Theoretical Computer Science |
Volume | 809 |
Online published | 31 Dec 2019 |
Publication status | Published - 24 Feb 2020 |
Link(s)
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 (i + 1)n − 2i for i = 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 (i + 1)n − 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.
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 journal › peer-review