Mobius超立方体网络的Hamilton分解

互连网络是超级计算机的重要组成部分,在设计和选择一个互连网络时,Hamilton性是评估网络性能的一个重要指标,M?bius立方体作为最重要的互连网络拓扑结构之一,也具有优良的Hamilton性,师海忠提出两个猜想:猜想1:M?bius立方体网络nMQ是Hamilton可分解的;猜想2:当n=2k( k≥2)时,nMQ是边不交的i(1≤i≤k)个Hamilton圈和n-2i个完美匹配的并;当n=2k+1(k≥1)时,nMQ是边不交的i(￡i)1￡k个Hamilton圈和n-2i个完美匹配的并。当i=k时,猜想2即为猜想1。本文将对n=3,4,5时,证明猜想1和猜想2是正确的,当n=6;i=1,2时,猜想2是成立的。

Mbius立方体上一个新圈的构造算法

The process of finding Hamilton paths in the n-dimensional Mbius cube was studied,and the relative algorithm of the cycle-embedding of length l (4≤ l ≤2\+ n )into the n-dimensional Mbius cube was also given.The time complexity of this algorithm is O( l ).It is much lower than the time complexity O(NlogN),N=2\+ n ,which Fan Jianxi has given to us.

关于超立方体与Mbius立方体的连接

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究.超立方体及其变型——Mbius立方体两者都具有优点,也具有缺点.本文给出了在超立方体与Mbius立方体的顶点之间的一种连接,从而得到一种称为HMm-立方体的新型网络,证明了HMn-立方体不仅保持了超立方体和Mbius立方体的低顶点度数和高连通度以及其直径至多比Mbius立方体大2的性质,而且它克服了超立方体对圈模拟能力的不足.

Mbius立方体互连网络上基于连通度的容错路由选择算法

Mbius立方体具有很多优越的性质,已经被用作多种并行机中处理器连接的拓扑结构并引起了国际上许多研究者的研究兴趣。处理机发生故障是难以避免的,其解决办法便是可容错技术,因此,给出一个好的容错路由选择算法也是非常必要的。本文以0-Mn为例给出一个Mbius立方体互连网络上基于连通度的容错路由选择算法,并分析该算法的时间复杂度为O(n)。