Geodesic
New Bounds for Oblivious Mesh Routing
Journal of Graph Algorithms and Applications, Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications , Tome 5 (2001) no. 5, pp. 17-38.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 two-dimensional, $\sqrt{N} \times \sqrt{N}$ mesh with constant queue-size. This is the first algorithm which improves substantially the trivial $O(N)$ bound for oblivious routing in the mesh networks with constant queue-size. The other is a $1.16 \sqrt{N} + o(\sqrt{N})$ algorithm on the three-dimensional, $N^{1/3} \times N^{1/3} \times N^{1/3}$ mesh with unlimited queue-size. 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. 
@article{JGAA_2001_5_5_a2,
     author = {Kazuo Iwama and Yahiko Kambayashi and Eiji Miyano},
     title = {New {Bounds} for {Oblivious} {Mesh} {Routing}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {17--38},
     publisher = {mathdoc},
     volume = {5},
     number = {5},
     year = {2001},
     doi = {10.7155/jgaa.00038},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00038/}
}
TY  - JOUR
AU  - Kazuo Iwama
AU  - Yahiko Kambayashi
AU  - Eiji Miyano
TI  - New Bounds for Oblivious Mesh Routing
JO  - Journal of Graph Algorithms and Applications
PY  - 2001
SP  - 17
EP  - 38
VL  - 5
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00038/
DO  - 10.7155/jgaa.00038
LA  - en
ID  - JGAA_2001_5_5_a2
ER  - 
%0 Journal Article
%A Kazuo Iwama
%A Yahiko Kambayashi
%A Eiji Miyano
%T New Bounds for Oblivious Mesh Routing
%J Journal of Graph Algorithms and Applications
%D 2001
%P 17-38
%V 5
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00038/
%R 10.7155/jgaa.00038
%G en
%F JGAA_2001_5_5_a2
Kazuo Iwama; Yahiko Kambayashi; Eiji Miyano. New Bounds for Oblivious Mesh Routing. Journal of Graph Algorithms and Applications, 
							Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications
					, Tome 5 (2001) no. 5, pp. 17-38. doi : 10.7155/jgaa.00038. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00038/

Cité par Sources :