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

• 作者: 吴敏 喻昕 王国军
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 交叉立方体 超立方体 互联网络 最短路径 路由算法
• 年，卷（期）: 2007,（4）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 615-621
• 页数: 7页
• 分类号: TP393
• 字数: 7762字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2007.04.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴敏	中南大学信息科学与工程学院	439	5230	34.0	47.0
2	王国军	中南大学信息科学与工程学院	123	760	12.0	19.0
3	喻昕	中南大学信息科学与工程学院	8	43	3.0	6.0