| 一种新的交叉立方体最短路径路由算法 |
| |
| 引用本文： | 喻昕,吴敏,王国军. 一种新的交叉立方体最短路径路由算法[J]. 计算机学报, 2007, 30(4): 615-621 |
| |
| 作者姓名： | 喻昕 吴敏 王国军 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083;中南大学信息科学与工程学院,长沙,410083;中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金 , 教育部优秀青年教师资助计划 |
| |
| 摘 要： | Efe提出的交叉立方体(crossed cube)是超立方体(hypercube)的一种变型.交叉立方体的某些性质优于超立方体,比如其直径几乎是超立方体的一半.Efe提出了时间复杂度为O(n2)的交叉立方体最短路径路由算法.Chang等人扩展了Efe的算法,时间复杂度为O(n),它在路由的每一步有更多条边作为最短路径可供寻路选择.但这些边并没有包含全部可进行最短路径路由的边.文中给出了结点各边可进行最短路径路由的充要条件,并在此基础上提出了一种时间复杂度为O(n2)的交叉立方体最短路径路由算法,它在路由的每一步都将所有的最短路径边作为候选边.理论分析和实例表明它可输出任意一条最短路径.
|
| 关 键 词： | 交叉立方体 超立方体 互联网络 最短路径 路由算法 |
| 修稿时间： | 2006-02-052006-12-10 |
A Novel Shortest Path Routing Algorithm in the Crossed Cube |
| |
| YU Xin,WU Min,WANG Guo-Jun. A Novel Shortest Path Routing Algorithm in the Crossed Cube[J]. Chinese Journal of Computers, 2007, 30(4): 615-621 |
| |
| Authors: | YU Xin WU Min WANG Guo-Jun |
| |
| Affiliation: | School of Information Science and Engineering, WANG Guo-Jun Central South University, Changsha 410083 |
| |
| Abstract: | |
| |
| Keywords: | crossed cube hypercube interconnection networks shortest path routing algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
