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

摘要：

Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型,其某些性质优于超立方体,比如其直径几乎是超立方体的一半.在高性能的并行计算机系统中,信息是通过若干条结点互不交叉的路径并行传输,并且网络中的结点和链路出错是不可避免的,因此这些路径的长度将直接影响并行计算的性能.本文对交叉立方体的内顶点互不交叉路径进行了研究,证明了以下结论:在n维交叉立方体CQn中任意两顶点u,v间存在n条内顶点互不交叉的路径, 使得(1)最短路的长度=u和v之间的距离, (2)所有路中的最长路径长度≤u和v的距离+4. 这说明交叉立方体互连网络具有很好的并行通信性能和容错性能.

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

所属期刊栏目：28

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金60425310;教育部优秀青年教师资助计划教人[2002]5号

在线出版日期：2007-09-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1382-1386