An Algorithm to Find Optimal Double-Loop Networks with Non-unit Steps

摘要：

A double-loop network (DLN) G (N; r, s) is a digraph with the vertex set V=0,1,...,N-1 and the edge set E=v→v+r(mod N) and v→v+s(mod N)|v∈V. Let D(N; r, s) be the diameter of G, D(N)=minD(N; r, s)|1≤r<s<N and gcd (N; r, s)=1 and D<,1>(N)=minD(N; 1, s)|1<s <N. Although the identity D(N)=D<,1>(N) holds for infinite values of N, there are also another infinite set of integers with D(N)<D<,1>(N). These other integral values of N are called non-unit step integers or nus integers. Xu and Aguilo et al. gave some infinite families of 0-tight nus integers with D <,1>(N)-D(N)≥1. In this work, an algorithm is derived for finding nus integers. The running time complexity of the proposed algorithm is O(k<2>)O(N<1/4>log N). It is verified by computer that the algorithm works extremely well. A new approach is also proposed for finding infinite families of nus integers. As an example, we present an infinite family of of 0-tight nus integers with D <,1>(N)-D(N)=4.

关键词： Double-loop network tight optimal L-shaped tile non-unit step integer algorithm

作者: Xiaoping Dai Jianqin Zhou Kaihou Wang

作者单位: Department of Computer Science, Anhui University of Technology Maanshan, 243002 China Department of Mathematics, Shijiazhuang University of Economics Shijiazhuang, 050031 China

会议类型: 国际会议

会议名称: 7th International Symposium,APPT 2007(第7届高级并行处理技术大会)

会议地点: 广州

会议语种:英文

页码: 352-361

在线出版日期: 2007-11-22（万方平台首次上网日期，不代表论文的发表时间）