TY - JOUR

T1 - An O(log3N) Algorithm for Reliability Assessment of 3-Ary n-Cubes Based on h-Extra Edge Connectivity

AU - Xu, Liqiong

AU - Zhou, Shuming

AU - Hsieh, Sun Yuan

N1 - Publisher Copyright:
© 1963-2012 IEEE.

PY - 2022/9/1

Y1 - 2022/9/1

N2 - Reliability evaluation of multiprocessor systems is of great significance to the design and maintenance of these systems. As two generalizations of traditional edge connectivity, extra edge connectivity and component edge connectivity are two important parameters to evaluate the fault-tolerant capability of multiprocessor systems. Fast identifying the extra edge connectivity and the component edge connectivity of high order remains a scientific problem for many useful multiprocessor systems. In this article, we determine the h-extra edge connectivity of the 3-ary n-cube Qn3 for h\in [1, frac3n-12]. Specifically, we divide the interval [1, frac3n-12] into some subintervals and characterize the monotonicity of λ h(Qn3) in these subintervals and then deduce a recursive closed formula of λ h(Qn3). Based on this formula, an efficient algorithm with complexity O(log 3\,N) is designed to determine the exact values of h-extra edge connectivity of the 3-ary n-cube Qn3 for h [1, 3n-12] completely. Moreover, we also determine the g-component edge connectivity of the 3-ary n-cube Qn3(n ≥q 6) for 1 ≤ g ≤ 3n2 .

AB - Reliability evaluation of multiprocessor systems is of great significance to the design and maintenance of these systems. As two generalizations of traditional edge connectivity, extra edge connectivity and component edge connectivity are two important parameters to evaluate the fault-tolerant capability of multiprocessor systems. Fast identifying the extra edge connectivity and the component edge connectivity of high order remains a scientific problem for many useful multiprocessor systems. In this article, we determine the h-extra edge connectivity of the 3-ary n-cube Qn3 for h\in [1, frac3n-12]. Specifically, we divide the interval [1, frac3n-12] into some subintervals and characterize the monotonicity of λ h(Qn3) in these subintervals and then deduce a recursive closed formula of λ h(Qn3). Based on this formula, an efficient algorithm with complexity O(log 3\,N) is designed to determine the exact values of h-extra edge connectivity of the 3-ary n-cube Qn3 for h [1, 3n-12] completely. Moreover, we also determine the g-component edge connectivity of the 3-ary n-cube Qn3(n ≥q 6) for 1 ≤ g ≤ 3n2 .

UR - http://www.scopus.com/inward/record.url?scp=85112602786&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85112602786&partnerID=8YFLogxK

U2 - 10.1109/TR.2021.3089466

DO - 10.1109/TR.2021.3089466

M3 - Article

AN - SCOPUS:85112602786

SN - 0018-9529

VL - 71

SP - 1230

EP - 1240

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

IS - 3

ER -