On conditional fault tolerance and diagnosability of hierarchical cubic networks

详细信息    查看全文

• 作者：Shuming Zhou^a ; ^b ; ^{zhoushuming@fjnu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Sulin Song^a ; ^b ; Xiaoxue Yang^b ; ^c ; Lanxiang Chen^a ; ^b
• 关键词：Fault tolerance ; Conditional connectivity ; Conditional diagnosability ; Hierarchical cubic network
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P2
• 页码：421-433
• 全文大小：469 K

文摘

Fault tolerance is especially important for interconnection networks, since the growing size of networks increases their vulnerability to component failures. A classical measure for the fault tolerance of a network in the case of vertex failures is its connectivity. Given a network based on a graph G and a positive integer h  , the 7515009366&_mathId=si1.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=59987a6d61f506c16f5735be88cd171d" title="Click to view the MathML source">R^hhContainer hidden">$R^h$-connectivity of G is the minimum cardinality of a set of vertices in G, if any, whose deletion disconnects G, and the minimum degree of every connected component is at least h  . This paper investigates the 7515009366&_mathId=si1.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=59987a6d61f506c16f5735be88cd171d" title="Click to view the MathML source">R^h$R^h$-connectivity (7515009366&_mathId=si2.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=5ee8aedfc4d225b5ed23b12356a9a1e3" title="Click to view the MathML source">h=1,2$h=1,2$) of the hierarchical cubic network 7515009366&_mathId=si3.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=f64d2fdf87e0eda21c1cdc1b661a54f8" title="Click to view the MathML source">HCN_n${\mathit{HCN}}_n$ (7515009366&_mathId=si4.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=86f1d030bb45539f5c1937833f4e2e4d" title="Click to view the MathML source">n≥2$n\ge 2$), and shows that 75" class="mathmlsrc">7515009366&_mathId=si175.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=a6f59763d875028714f2fe7bddea3b5c" title="Click to view the MathML source">κ¹(HCN_n)=2n, 7515009366&_mathId=si328.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=44bf29edcc33eb57b384891f002d9bd5" title="Click to view the MathML source">κ²(HCN_n)=4n−4${\kappa }^2({\mathit{HCN}}_n)=4n-4$, respectively. Furthermore, the paper establishes the conditional diagnosability of 7515009366&_mathId=si3.gif&_user=111111111&_pii=S0304397515009366&_rdoc=1&_issn=03043975&md5=f64d2fdf87e0eda21c1cdc1b661a54f8" title="Click to view the MathML source">HCN_n${\mathit{HCN}}_n$ under the PMC diagnostic model.