The problem of finding optimal diameter double loop networks with a fixed number of vertices has been widely studied. In this work, we give an algorithmic solution of the problem by using a geometrical approach.
Given a fixed number of vertices n, the general problem is to find "steps" s 1 , s z e ~',, such that the digraph G(n; sl,s2) with set of vertices V = 7/and adjacencies given by i ~ i + s I (mod n) and i --* i + s 2 (mod n) has minimum diameter d(n). A lower bound of this diameter is known to be lb(n) = [x/~n 7 -2. So, given n, the algorithm has as outputs sl, s2 and the minimum integer K = Kin) such that
The running time complexity of the algorithm is O(
Moreover, in most of the cases the algorithm also gives (as a by-product) an infinite family of digraphs with increasing order and diameter as above, to which the obtained digraph G(n; sl, s2) belongs. et al. [2] or Hwang [8]. The digraphs that model such networks are usually called double fixed step or circulant digraphs. A double fixed-step digraph with n vertices, Work supported by the Spanish Research Council (Comision Interministerial de Ciencia y Tecnologia, CICYT) under project TIC90-0712.