几类特殊有向单位步长双环网络的寻径算法  

Routing algorithm of several kinds of special double-loop networks with unit step

作　　者：边琼芳[1] 

机构地区：[1]安徽工业大学计算机学院,安徽马鞍山243002

出　　处：《计算机工程与设计》2012年第11期4062-4065,共4页Computer Engineering and Design

基　　金：国家自然科学基金项目(60473142)

摘　　要：直径的求解是双环网络的最关键问题,为更好求解双环网络直径,文中选择一个步长为1的有向单位步长双环网络,针对另一个步长h的取值为最小值2,中间值N/2、(N/2)+1(N为偶数)或者中间值(N+1)/2(N为奇数)和最大值N-1这3种情况所构成的几类双环网络,给出了寻径算法,对这几种算法的特点进行了分析和比较,并对这几种算法的时间和空间特性进行了比较分析,得出它们的时间复杂度和空间复杂度都是Ω(N/2)。Abstract： The diameter of the solution is the most critical issue of the double loop networks, in order to get the better solution for the double loop network diameter, select a step size of I to unit step double loop networks, in allusion to another step h of the value for the minimum value of 2, the middle valueN/2, （N/2 ＋ 1, （N is even ） or the middle value （N＋ 1）/2 （N is odd） and maximum value N-1 , these three circs constitute the class of double loop networks, routing algorithm are proposed, and analyzes the characteristics of these different kinds of algorithms and comparison, and the temporal and spatial characteristics of these types of algorithms are compared and analyzed. Time complexity degrees and storage complexity degrees are both result in Ω （N/2）.

关 键 词：特殊有向单位步长 双环网络 寻径 算法 时间空间特性 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]