摘要
作为超立方体的变型 ,交叉立方体同时具有一些比超立方体优越的性质 ,但类似于超立方体 ,它的升级也伴随着顶点个数的增加而成倍增加 .为了解决这一问题 ,一种称为超级交叉立方体 (SCC)的互连网络被提了出来 .有关文献已证明 ,SCC很好地保持了交叉立方体在顶点度数 ,直径和连通度方面的优越性质 ,而且其升级可以增加任意多个顶点 .用图嵌入技术讨论了 SCC模拟环网络的能力 ,证明了长度为 4到 N的任一圈都能以扩张 1嵌入具有 N个顶点的 SCC,从而证明了 SCC模拟环网络的能力与交叉立方体完全相同 .
As a hypercube variation, the crossed cube has some superior properties over the hypercube. For example, the diameter of the crossed cube is approximately half that of the hypercube; the complete binary tree with 2\+ n -1 nodes can be embedded into the n \|dimensional crossed cube with dilation 1, etc.. So it is attractive in the parallel processing area. However, similar to the hypercube, it is necessary to double the number of nodes to upgrade the crossed cube. In order to solve this problem, a kind of interconnection networks, named the super crossed cubes(SCC), is proposed. It is proved that the SCC well retain the advantageous properties that the crossed cube possesses in the respect of the node degrees, the diameter, and the connectivity, and it only needs to add arbitrary number of nodes to upgrade the SCC. The ability of the SCC to simulate a kind of important parallel architectures—ring networks—is discussed by using the graph\|embedding technique in this paper. It is proved that any cycle with length 4 through N are all able to be embedded with dilation 1 into the SCC of N nodes. Thus, it is shown that the ability of the SCC to simulate ring networks is the same as the crossed cube.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2000年第12期1477-1481,共5页
Journal of Computer Research and Development
基金
山东省青年科学基金资助!(项目编号 Q99G12 )
关键词
互连网络
交叉立方体
图嵌入
计算机网络
interconnection network, crossed cube, super crossed cube, graph embedding, dilation, cycle(
