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$.