A Fast Algorithm to Find Optimal Double-Loop Networks

Double-loop networks have been widely studied as architecture for local area networks. A double-loop digraph G(N; s₁, s₂) has N vertices 0, 1,..., N-l and 2N edges of two types: s₁-edge: i¿1 + s (mod N); i=0, 1,..., N-l, and s₂-edge: i¿ s + s₂ (modN); i=0, 1,..., N-l, for some fixed steps 1¿ s₁<s₂<N with gcd(N; s₁, s₂) = 1. Let D(N; s₁, s₂) be the diameter of G and let us define D(N) = min{ D(N; s₁, s₂) | 1¿s₁<s₂<N and gcd(N; s₁, s₂) = 1} and D(N) = min{D(N; 1, s)| 1<s<N}. Given a fixed number of vertices N, the general problem is to find steps s₁ and s₂, such that the digraph G(N; s₁, s₂) has minimum diameter D(N). A lower bound of this diameter is known to be lb(N)= [¿(3N)]-2. In this work, we give a simple and efficient algorithmic solution of the problem by using a geometrical approach. Given n, the algorithm has outputs s₁, s₂ and the minimum integer k=k(N), such that D(N; s₁, s₂ )=D(N)=lb(N)+k. The running time complexity of the algorithm is 0(k² )0(N^1/4 logN). Also, some flaws in the bibliography are corrected.