The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
On Rearrangeability of Multirate Clos Networks
Guo-Hui Lin, Ding-Zhu Du, Xiao-Dong Hu, Guoliang Xue,
Pages. 1225-1231
Abstract Chung and Ross [SIAM J. Comput., 20 (1991), pp, 726-736] conjectured that the multirate three-stage Clos network $C(n,2n-1,r)$ is rearrangeable in the general
discrete bandwidth case; i.e., each connection has a weight chosen from a given
finite set ${p_i,p_2,...,p_k}$ where $1 geq p_1> p_2>cdots > p_k>0$ and
$p_i$ is an integer multiple of $p_k$, denoted by $p_k|p_i$, for $1 leq i leq
k-1$. In this paper, we prove that multirate three-stage Clos network
$C(n,2n-1,r)$ is rearrangeable when each connection has a weight chosen from a
given finite set ${p_i,p_2,...,p_k}$ where $1geq p_1>p_2>cdots > p_h>1/2geq
p_{h+1}>cdots>p_k>0$ and $p_{h+2}|p_{h+1},p_{h+3}|p_{h+2},...,p_k|p_{k-1}$. We also prove that $C(n,2n-1,r)$ is two-rate rearrangeable and $C(n,lceil
frac{7n}{3}rceil,r)$ is three-rate rearrangeable.
Contents 1. Introduction
2. Main results
3. Discussion
Key words rearrangeability, multirate Clos networks, minimization of the number of center switches
Mathmatical Subject Classification 94A05, 05C70