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

A Fast Routing Algorithm for Supertoroidal Networks

作　　者：陈宝兴[1] 肖文俊[1] 

机构地区：[1]厦门大学数学系,福建厦门361005

出　　处：《厦门大学学报（自然科学版）》2003年第1期14-20,共7页Journal of Xiamen University：Natural Science

基　　金：漳州师院科研经费资助

摘　　要：利用环状网络(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.

关 键 词：快速路由算法 CAYLEY图 超圆环面 环状网络 最矩路径 计算机互连网络 时间复杂性 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]