Some Optimal Designs of Undirected Double-Loop Networks

Baoxing Chen 1, 2, Jixiang Meng 1, and Wenjun Xiao 3
1 College of Mathematics System Science, XinJiang University, Wulumuqi, P. R. China
2 Department of Computer Science, Zhangzhou Teacher's College, Zhangzhou, P. R. China
3 Department of Computer Science, South China University of Technology, Guangzhou, P. R. China

Abstract     Full Text  PDF

Let $n,s$ be positive integers such that $2\leq s< n$ and $s\neq n/2$. An undirected double-loop network $G(n; \pm 1, \pm s)$ is an undirected graph $(V, E)$, where $V$=$\mathbb Z_n$=$\{0, 1, 2, \ldots , n-1 \}$, $E$=$\{ i$ $ \rightarrow i+1 \pmod n, i \rightarrow i-1 \pmod n,$\\$ i \rightarrow i+s \pmod n$, $i\rightarrow i-s \pmod n \ | \ i=0, 1, 2, \ldots , n-1 \}$. An attention deserving problem is: for a given positive integer $n$, how to choose an integer $s$ such that the diameter of $G(n; \pm 1, \pm s)$ is minimal. An $O(k^3 \sqrt{n} \log \ n)$ algorithm, where $k$ is upper-bounded by $O(n^{0.25})$, is given in this paper to determine $s$ such that the diameter of $G(n; \pm 1, \pm s)$ is minimal.