交叉立方体内顶点不交叉路径长度的研究  

Research on the Lengths of Crossed Cube Internally Vertex-disjoint Paths

作　　者：喻昕[1] 吴敏[1] 王国军[1] 付朝晖[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《小型微型计算机系统》2007年第8期1382-1386,共5页Journal of Chinese Computer Systems

基　　金：国家杰出青年科学基金项目(60425310)资助;教育部青年教师奖励计划项目(教人[2002]5号)资助

摘　　要：Efe提出的交叉立方体(crossedcube)是超立方体(hypercube)的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半.在高性能的并行计算机系统中,信息是通过若干条结点互不交叉的路径并行传输,并且网络中的结点和链路出错是不可避免的,因此这些路径的长度将直接影响并行计算的性能.本文对交叉立方体的内顶点互不交叉路径进行了研究,证明了以下结论:在n维交叉立方体CQn中任意两顶点u,v间存在n条内顶点互不交叉的路径,使得(1)最短路的长度=u和v之间的距离,(2)所有路中的最长路径长度≤u和v的距离+4.这说明交叉立方体互连网络具有很好的并行通信性能和容错性能.The crossed cube proposed by Efe is a variation of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is approximately half that of the hypercube. The messages are simultaneously transmitted on some internally vertex-disjoint paths in the high performance parallel computing system, and the failures of nodes or links are inevitable, thus the lengths of those paths directly affect the performance of parallel computing. We prove the conclusion that for any pair of vertexes in an n-dimensional crossed cube CQn, there exist n internally vertex-disjoint paths, such that (1) the length of the shortest path= the distance of the pair vertexes, (2) the length of each path ≤the distance of the pair vertexes+4. Therefore, the interconnection network of crossed cube has high performance of communication and fault tolerance.

关 键 词：交叉立方体 超立方体 顶点不交叉路径 路径长度 容错性 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]