摘要：本文讨论具有大最错误结点的超立方体网络中的并行路由算法.假定H<,n>是一个局部k-维子立方体连通的n-维超立方体网络,本文提出的并行路由算法能够找出至少K=min(D<,k>(u),D<,k>(v))条并行路径,其中每一条路径的长度不超过(d<,H>(U<,k>,V<,k>)+3)2<'k>.该算法的时间复杂度为O(Kn2<'k>).这里,D<,k>(u)和D<,k>(v)分别代表源结点u和目的结点v的正确的邻结点个数(不考虑u和v所在的k-维子立方体内部的邻结点),d<,H>(U<,k>V<,k>)代表源结点u和目的结点v所在的两个k-维子立方体U<,k>和V<,k>之间的海明距离.本文还考察了k=3的特殊情况,在k=3并且有分别不超过12.5﹪和25﹪的错误结点的情况下,该算法的时间复杂度为O(Kn),并且每一条路径的路径长度分别在大约1.5和2倍源结点和目的结点之间的海明距离之内.该算法只要求结点知道其邻结点的状态,而无需知道整个网络信息,也就是说,该算法是基于局部信息的,因而该算法具有很强的实际意义.
