http://tracker.cse.buffalo.edu/Ticket/Display.html?id=9912

Remote host: saigon.cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%U /tmp/cr.ps
%A Ngo, Hung Q.
%A  Vu, Van H.
%T On Multi-rate Rearrangeable Clos Networks and a Generalized Edge Coloring Problem on Bipartite Graphs
%R 2002-07
%D May 10, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Multirate Rearrangeability, Clos Networks, Bipartite Graph Edge Coloring
%X Chung and Ross (SIAM J. Comput., \textbf{20}, 1991) 
conjectured that the minimum number 
$m(n,r)$ of middle-state switches for the symmetric $3$-stage Clos network 
$C(n,m(n,r),r)$ to be rearrangeable in the multirate enviroment is 
at most $2n-1$. 
This problem is equivalent to a generalized version of the bipartite 
graph edge coloring problem. 
The best bounds known so far on this function $m(n,r)$ is 
$11n/9 \leq m(n,r) \leq 41n/16 + O(1)$, for $n, r \geq 2$, derived 
by Du-Gao-Hwang-Kim (SIAM J. Comput., \textbf{28}, 1999). 
In this paper, we make several contributions. Firstly, we give evidence 
to show that even a stronger result might hold. 
In particular, we show that $m(n,r) \leq \lceil (r+1)n/2 \rceil$, which implies 
$m(n,2) \leq \lceil 3n/2 \rceil$ - 
stronger than the conjectured value of $2n-1$. 
Secondly, we derive that $m(2,r) = 3$ by an elegant argument. 
Lastly, we improve both the best upper and lower bounds given above: 
$\lceil 5n/4 \rceil \leq m(n,r) \leq 2n-1+\lceil (r-1)/2 \rceil$, 
where the upper bound is an improvement 
over $41n/16$ when $r$ is relatively small compared to $n$. 
We also conjecture that $m(n,r) \leq \lfloor 2n(1-1/2^r) \rfloor$.