超圆环面的一种快速路由算法

A Fast Routing Algorithm for Supertoroidal Networks

利用环状网络(Loopnetworks)到超圆环面的两种嵌入及环状网络的最优路由算法,给出了一种新的超圆环面的快速路由算法,其时间复杂性仅为O(D)(这里D为网络的直径).当r≥2时,此算法得到的任两个结点的路径长度path＿long≤[cr/2]+[kc/2]+1.特别地,当r≥2,c≥8时,path＿long≤D+1.

In this paper, by using two embeddings of loop networks into the supertoroidal networks and an optimal routing for the loop networks, we give an O(D) time fast routing algorithm for supertoroidal networks(where D is the diameter of the networks). We also show that if r≥2 and c≥8, the length of the path between any two nodes given by our algorithm is not more than D+1.