《计算机学报》文章摘要   全文下载
  文章题目N-Star网络中最优的点到多点平行路由算法
  作者杨义先1) 刘焕平2) 吴伟陵1)
  作者单位1)(北京邮电大学信息安全中心 北京 100876) 2)(哈尔滨工业大学计算机科学与工程系 哈尔滨 150001)
  发表年份1999
  发表月份8期　（页码：785—791)
  文章摘要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(2in),而且无论在时间上还是在生成路的长度上,均是最优的. 关键词 n-Star网络,互连网络,并行路由算法,内部无交路.