一种新的交叉立方体最短路径路由算法

摘要：

Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.Efe提出了时间复杂度为O(n2)的交叉立方体最短路径路由算法.Chang等人扩展了Efe的算法,时间复杂度为O(n),它在路由的每一步有更多条边作为最短路径可供寻路选择.但这些边并没有包含全部可进行最短路径路由的边.文中给出了结点各边可进行最短路径路由的充要条件,并在此基础上提出了一种时间复杂度为O(n2)的交叉立方体最短路径路由算法,它在路由的每一步都将所有的最短路径边作为候选边.理论分析和实例表明它可输出任意一条最短路径.

关键词：交叉立方体、超立方体、互联网络、最短路径、路由算法

所属期刊栏目：30

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

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

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

页数：共7页

页码：615-621