Reliability measures in relation to the h-extra edge-connectivity of folded hypercubes

详细信息    查看全文

• 作者：Mingzu Zhang ^{mzuzhang@163.com" class="auth_mail" title="E-mail the corresponding author} ; Lianzhu Zhang ; ^{zhanglz@xmu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Xing Feng ^{fengxing_fm@163.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Fault tolerance ; Extra edge-connectivity ; Folded hypercube ; Multiprocessor
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：15 February 2016
• 年：2016
• 卷：615
• 期：Complete
• 页码：71-77
• 全文大小：271 K

文摘

The folded hypercube le="Click to view the MathML source">FQ_n${\mathit{FQ}}_n$, as a variation of the hypercube le="Click to view the MathML source">Q_n$Q_n$, was proposed by A. El-Amawy and S. Latifi in 1991. The h  -extra edge-connectivity of the underlying topological graph of a multiprocessor system is a kind of measure for the reliability of the multiprocessor system. In this paper, we determine the exact value of le="Click to view the MathML source">λ_h(FQ_n)${\lambda }_h({\mathit{FQ}}_n)$ for integer h  , le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si174.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=ec1367fd46b1e39f0a1876b9116cba46">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si174.gif">$1\&<font\; color="red">le</font>;h\&<font\; color="red">le</font>;2^{\lceil \frac{n}{2}\rceil +1}$ and le="Click to view the MathML source">6&le;n$6\&<font\; color="red">le</font>;n$, which generalizes several known results for le="Click to view the MathML source">h&le;n$h\&<font\; color="red">le</font>;n$. More interestingly, we also show that le="Click to view the MathML source">λ_h(FQ_n)${\lambda }_h({\mathit{FQ}}_n)$ is the constant le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si49.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=16507fede6d9635204aafe10f92cdb51">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si49.gif">$(\lceil \frac{n}{2}\rceil -r+1)2^{\lfloor \frac{n}{2}\rfloor +r}$ for le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si192.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=e2949cd999756bc3290b0b3f21e596c7">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si192.gif">$2^{\lfloor \frac{n}{2}\rfloor +r}-l_r\&<font\; color="red">le</font>;h\&<font\; color="red">le</font>;2^{\lfloor \frac{n}{2}\rfloor +r}$, where le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si146.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=df8b7633c756c4e4eb3cf5d6a6ed6ee5">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si146.gif">$r=1,2,\dots ,\lceil \frac{n}{2}\rceil -1$ and le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si10.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=1080a226c04cbb996b90c7d6948148d7">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si10.gif">$l_r=\frac{2^{2r}-1}{3}$ if n   is odd and le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si11.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=cf418b1ec93c784d95260d8755735840">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si11.gif">$l_r=\frac{2^{2r+1}-2}{3}$ if n   is even. In particular, for le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si12.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=69093b4790fda941ca6d32fecf3ea3fa">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si12.gif">$r=\lceil \frac{n}{2}\rceil -1$, le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515011378&_mathId=si13.gif&_user=111111111&_pii=S0304397515011378&_rdoc=1&_issn=03043975&md5=b9b42f1e2d4bcf1f91ce239ecbff500e">le="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397515011378-si13.gif">$\lfloor \frac{2^n+2}{3}\rfloor \&<font\; color="red">le</font>;h\&<font\; color="red">le</font>;2^{n-1}$, le="Click to view the MathML source">λ_h(FQ_n)=2ⁿ${\lambda }_h({\mathit{FQ}}_n)=2^n$.