超级扭立方体互连网络及其性质

扭立方体是超立方体的一类变体,它具有比超立方体更好的性质。但是,同超立方体一样,它也是具有2n个顶点的n-正则图,故要使一个扭立方体的维数(即顶点度数)增加1(称为升级),就必须成倍地增加扭立方体中的顶点个数。为了解决这一问题,将具有2n个顶点的扭立方体的拓扑结构加以改变,得到了包含任意多个顶点的互连网络——超级扭立方体(STN)。证明了超级扭立方体保持了扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质、连通度级的tp-可诊断度等方面的优良性质,更进一步地,由于它包含了任意多个顶点,所以对它的升级只需增加任意多个顶点,从而克服了扭立方体的升级必须成倍增加其顶点个数的缺点。     

HCH-立方体的Hamilton连通性

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的。这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。     

超级局部扭立方体互连网络及其性质

局部扭立方体是近年来提出的超立方体的一个变型,由于它的许多优越性质(如低直径),在并行处理领域越来越受到人们的重视.然而,像超立方体一样,它也有一个缺点,即要使局部扭立方体升级,就必须成倍地增加其顶点个数.为了解决这一问题,文中将顶点个数为2的次幂的局部扭立方体推广到具有任意个顶点的互连网络,提出了超级局部扭立方体(SLTC)的定义,并证明它保持了局部扭立方体的最高连通度、对数级的直径和顶点度数、Hamilton性质等方面的优良性质,从而证明了超级局部扭立方体是既保持了局部扭立方体的多种优越性质又易于升级的互连网络.     

交叉扭立方体互联网络及其性质

扭N立方体是近年来提出的一种新型变体网络结构.通过X-变换操作使得存在2n个顶点的超立方体的网络直径从N减少到N-1,减少了网络规模增大时所需要的网络开销,从而受到了广泛的欢迎.与超立方体一样,扭N立方体也存在缺点,如果增加扭N立方体的维数,会成倍增加扭N立方体的顶点个数.为了解决这一问题,本文通过扭N立方体的结构,提出了交叉扭立方体的定义,并给出了相应的拓扑结构网络图,证明了交叉扭立方体的部分子网与超立方体网络同构,同时研究了交叉扭立方体的网络直径、连通度等问题.通过上述拓扑结构的基本性质的研究,得到了交叉扭立方体的性能优于扭N立方体的重要结论.     

平衡超立方体的故障容错性

故障容错是衡量多处理器互连网络可靠性的重要方式之一。其中g-限制边连通度和g-限制连通度保证了剩下每个分支之间不连通且每个分支中节点的邻居数目不少于 g,能够更加精准地测量多处理器和多信道系统的容错性和可靠性。平衡超立方体是超立方体的一个变形,它特有的良好拓扑性质能够更好地满足多处理器系统和多种新型网络的需要。提出了n维平衡超立方体的{1,2}-限制边连通度和{1,2}-限制连通度,能够丰富以平衡超立方体为拓扑结构的网络容错性和可靠性的评价体系,并为平衡超立方体的故障诊断算法打下良好基础。     

局部扭立方体环互连网络及其性质

优化网络的拓扑结构是互连网络研究的重要研究方向。局部扭立方体（locally twisted cube,LTQn ）是对超立方体（hypercube,Qn ）互连网络的优化变种,然而当对LTQn 升级时,需要成倍地增加网络的节点,这不利于LTQn的应用和发展。为了克服LTQn 这一缺陷,提出了一种新的互连网络拓扑结构：局部扭立方体环互连网络（locally twisted cube-connected ring interconnect network,LRN）,给出了LRN的定义及其拓扑结构,并研究了LRN的网络直径、连接度、汉密尔顿连通性、泛圈性、路由等问题,证明了LRN是一种易于升级又具有LTQn 许多优良性质的层次环互连网络（hierarchical ring interconnection networks,HRN）。     

二进制立方形递归网络的拓扑结构

二进制递归网络是一类具有良好拓扑性质和网络参数的互连网络模型.定义了一类特殊的二进制递归网络模型,即二进制立方形递归网络; 引入子网和超网的概念对其拓扑结构进行了分析研究; 证明了超立方体、扭n-立方体、广义扭立方体、交叉立方体、Mbius立方体和扭立方体连接网络都是这类特殊的二进制递归网络的具体实例.     

交叉立方体环的Hamilton连通性和Pancyclicity性

交叉立方体是超立方体互连网络的一种变型,它的某些性质优于超立方体。例如,其直径几乎是超立方体的一半;当n≥3,交叉立方体CQn具有Hamilton连通性;当n≥2,所有长度在4到2n之间的圈都能够以扩张1嵌入CQn,即交叉立方体具有Pancyclity性。但是,交叉立方体同超立方体一样,当需要升级时,必须成倍增加结点。交叉立方体环互连网络CRN作为层次环互连网络HRN[8]的一种,可以有效地克服这个缺点,当需要升级时,只需在环上增加一个交叉立方体。在文中,证明了交叉立方体环互连网络仍然保持了交叉立方体具有的Hamilton连通性和Pancyclity性。     

超级M(o)bius立方体一类最优容错的小直径互连网络

文中将具有2n个顶点的M(o)bius立方体的拓扑结构加以改变,得到了包含任意个顶点的互连网络--超级M(o)bius立方体,并证明它保持了M(o)bius立方体的高连通度、对数级的直径和顶点度数等优良性质,并且当顶点个数N=2n+2n-1 时,0-型超级M(o)bius立方体是一个(n+1)-正则图;更进一步地,由于它包含任意个顶点,所以其升级只需增加任意个顶点,从而克服了M(o)bius立方体的升级必须成倍增加其顶点个数的缺点.     

BC互连网络及其性质

提出一种称为一一对应连接（BC）图的互连网络族，使其包含超立方体、交叉立方体和Mobius立方体作为基具子集，同时又使其具有与超立方体、交叉立立体和Mobius立方体相同的对数级的直径和顶点度数、最高连通（容错）度和相同的可诊断性等性质，从而使对超立方体及与其结构相似的大量互连网络的某些性质的研究合而为一，证明了BC互连网络族中包含一类Hamilton连通图并给出了BC互连网族中的图的直径的一个猜想。     

超级交叉立方体互连网络及其拓扑性质

交叉立方体是近年提出的超立方体的一种变种。由于它的许多优越性质（如直径、嵌入性等）,在并行处理领域越来越受到人们的重视。然而,像超立方体一样,它也有一个缺点,即要使交叉立方体升级,就必须成倍地增加其顶点个数。为了解决这一问题,本文将顶点个数的２的次幂的交叉立方体推广到具有任意个顶点的互连网络,提出了超级交叉立方体的定义,并证明它保持了交叉立方体在高速通度、对数级的直径和顶点度数等方面的优良性质,从     

超级Mbius立方体──一类最优容错的小直径互连网络

文中将具有２ｎ个顶点的Ｍｏｂｉｕｓ立方体的拓扑结构加以改变,得到了包含任意个顶点的互连网络——超级Ｍｏｂｉｕｓ立方体,并证明它保持了Ｍｏｂｉｕｓ立方体的高连通度、对数级的直径和顶点度数等优良性质,并且当顶点个数Ｎ＝２ｎ＋２ｎ－１时,０－型超级Ｍｏｂｉｕｓ立方体是一个（ｎ＋１）－正则图;更进一步地,由于它包含任意个顶点,所以其升级只需增加任意个顶点,从而克服了Ｍｏｂｉｕｓ立方体的升级必须成倍增加其顶点个数的缺点．     

The twisted crossed cube

The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQ_n) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQ_n that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQ_n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ_n with crossed cube (CQ_n), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ_n/CQ_n and better properties in other respects, for example, its connection complexity is half of that of TCQ_n/CQ_n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ_n/CQ_n. Copyright © 2015 John Wiley & Sons, Ltd.     

The twisted-cube connected networks

This paper presents a new interconnection network topology,called the twisted-cube connected network,which is a generation of the twisted 3-cube.The twisted-cube connected network is a variant of the hyercube,and it has a better recursive structure.The regularity,connectivities,subgraphs of the twistedcube connected network are studied.The twisted-cube connected network is proved to be a 3-cube-free network,which is the essential difference from the hypercube and variants of the hypercube.An efficient routing algorithm is proposed,and the diameter of n-dimensional twisted-cube connected network is proved to be just[n 1/2] which is less than that of the hypercube.     

The connectivity of exchanged crossed cube

The exchanged crossed cube, proposed by Li et al., is a new interconnection network having better properties than other variations of hypercube in the area of the fewer diameter, smaller links and lower cost factor. In this work we will show that the connectivity of exchanged crossed cube is equal to its minimum degree. Moreover each smallest cut in exchanged crossed cube is a neighborhood of some vertex.     

The spined cube: A new hypercube variant with smaller diameter

Bijective connection graphs (in brief, BC graphs) are a family of hypercube variants, which contains hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes, etc. It was proved that the smallest diameter of all the known n-dimensional bijective connection graphs (BC graphs) is , given a fixed dimension n. An important question about the smallest diameter among all the BC graphs is: Does there exist a BC graph whose diameter is less than the known BC graphs such as crossed cubes, twisted cubes, Möbius cubes, etc., with the same dimension? This paper answers this question. In this paper, we find that there exists a kind of BC graphs called spined cubes and we prove that the n-dimensional spined cube has the diameter ⌈n/3⌉+3 for any integer n with n?14. It is the first time in literature that a hypercube variant with such a small diameter is presented.     

Fibonacci cubes-a new interconnection technology

A novel interconnection topology called the Fibonacci cube is shown to possess attractive recurrent structures in spite of its asymmetric and relatively sparse interconnections. Since it can be embedded as a subgraph in the Boolean cube (hypercube) and it is also a supergraph of other structures, the Fibonacci cube may find applications in fault-tolerant computing. For a graph with N nodes, the diameter, the edge connectivity, and the node connectivity of the Fibonacci cube are in the logarithmic order of N. It is also shown that common system communication primitives can be implemented efficiently