Name
Abstract | ||
|---|---|---|
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 2 ∈ Z n , such that the digraph G ( n ; s 1 , s 2 ) with set of vertices V = Z n and adjacencies given by i → i + s 1 ( mod n ) and i → i + s 2 ( mod n ) has minimum diameter d ( n ). A lower bound of this diameter is known to be be lb ( n )=⌈√3 n ⌉−2. So, given n , the algorithm has as outputs s 1 , s 2 and the minimum integer κ = κ ( n ) such that d ( n ; s 1 , s 2 )= d ( n )= lb ( n )+ κ The running time complexity of the algorithm is O ( κ 3 ) O ( log n )- O ( κ ) is unknown but it is upper-bounded by O (4√ n ). 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 ; S 1 , S 2 ) belongs. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0012-365X(95)94025-8 | Discrete Mathematics |
Keywords | DocType | Volume |
optimal double loop network,efficient algorithm,upper bound,lower bound,time complexity | Journal | 138 |
Issue | ISSN | Citations |
1 | Discrete Mathematics | 28 |
PageRank | References | Authors |
1.58 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| F. Aguiló | 1 | 56 | 5.74 |
| M. A. Fiol | 2 | 816 | 87.28 |