N-Star网络中最优的点到多点平行路由算法

• 作者: 刘焕平 吴伟陵 杨义先
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: n-Star网络 互连网络 并行路由算法 内部无交路
• 年，卷（期）: 1999,（8）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 785-791
• 页数: 7页
• 分类号: TP393
• 字数: 9045字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.1999.08.001

摘要

Chen等研究了n-Star网络中的点到多点并行路由问题,对前人的工作做了很大的改进,给出了一个几乎最优的时间复杂度为O(n2)的算法.由Chen的算法所给出的n-1条路P2,…,Pn满足|Pi|≤dist(v1,vi)+6,其中Pi是连接vi到v1的路,|Pi|表示路Pi的长度,dist(v1,vi)表示vi到v1的最短路的长度.作者进一步改进了Chen等的结果,给出了一个新的时间复杂度仍为O(n2)的算法,然而该算法给出的内部无交路P2,…,Pn满足|Pi|≤dist(v1,vi)+4(2≤i≤n),而且无论在时间上还是在生成路的长度上,均是最优的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨义先	北京邮电大学信息安全中心	629	8372	39.0	65.0
2	吴伟陵	北京邮电大学信息安全中心	251	1672	18.0	28.0
3	刘焕平	哈尔滨工业大学计算机科学与工程系	3	56	3.0	3.0