Home  Issues  Aims and Scope  Instructions for Authors 
Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications
DOI: 10.7155/jgaa.00038
New Bounds for Oblivious Mesh Routing
Vol. 5, no. 5, pp. 1738, 2001. Regular paper.
Abstract We give two, new upper bounds for oblivious permutation routing on the mesh networks: Let N be the total number of processors in each mesh. One is an $O( N^{0.75})$ algorithm on the twodimensional, $\sqrt{N} \times \sqrt{N}$ mesh with constant queuesize. This is the first algorithm which improves substantially the trivial $O(N)$ bound for oblivious routing in the mesh networks with constant queuesize. The other is a $1.16 \sqrt{N} + o(\sqrt{N})$ algorithm on the threedimensional, $N^{1/3} \times N^{1/3} \times N^{1/3}$ mesh with unlimited queuesize. This algorithm allows at most three bends in the path of each packet. If the number of bends is restricted to minimal, i.e., at most two, then the bound jumps to $\Omega( N^{2/3})$ as was shown in ESA'97.

Submitted: January 1999.
Revised: April 2000.
Revised: October 2000.
