| Presentation | 1998/4/24 Oblivious Routing Algorithms on Meshes Eiji MIYANO, Kazuo IWAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We give two, new upper bounds for oblivious permutation routing on the mesh network. One is an O(N^<0.75>) algorithm for the two-dimensional mesh with constant queue-size. This is the first algorithm which improves substantially the trivial O(N) bound. The other is an 1.16√N+o(√N)algorithm on the three-dimensional 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 it is known that the bound jumps to Ω(N^<2/3>). |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | oblivious routing / mesh / upper bound / queue-size / the number of bends |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1998/4/24(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Oblivious Routing Algorithms on Meshes |
| Sub Title (in English) | |
| Keyword(1) | oblivious routing |
| Keyword(2) | mesh |
| Keyword(3) | upper bound |
| Keyword(4) | queue-size |
| Keyword(5) | the number of bends |
| 1st Author's Name | Eiji MIYANO |
| 1st Author's Affiliation | Kyushu Institute of Design() |
| 2nd Author's Name | Kazuo IWAMA |
| 2nd Author's Affiliation | Department of Information Science Kyoto University |
| Date | 1998/4/24 |
| Paper # | |
| Volume (vol) | vol.98 |
| Number (no) | 36 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |