组合星图中一对一容错路由算法

A algorithm of node-to-node fault tolerant routing in the(n,k)-star

解决了组合星图的一对一容错路由问题.给出了故障节点不超过n-2时,无故障节点s到t的路由算法,证明了算法可以在O(n)内找到一条长度不超过D(Sn,k)+4的路P:s t,其中,D(Sn,k)是Sn,k的直径.运用列举法,推导出组合星图Sn,k中任意点p到固定点Ik的距离公式;并从图论的观点,推导出Sn,k任意2个子图之间的星边数目为(n-2)!/(n-k)!.

It is important for an interconnection network to route data among nodes despite faulty nodes in the network.Alternative paths in case of nodes failure can not only avoid communication bottlenecks,but increase the efficiency of message transmission.In this paper,we present a angorithm to find a faultless path st of length at most D(S_(n,k))+4 in O(n) time,given at most n-2 faulty nodes,also two distinct faultless nodes s and t in the (n,k)-star graph,where D(S_(n,k)) is the diameter of S_(n,k).