Hot-potato algorithms for permutation routing |
| |
| Authors: | Newman I. Schuster A. |
| |
| Affiliation: | Dept. of Math. & Comput. Sci., Haifa Univ. ; |
| |
| Abstract: | We develop a methodology for the design of hot-potato algorithms for routing permutations. The basic idea is to convert existing store-and-forward routing algorithms to hot-potato algorithms. Using it, we obtain the following complexity bounds for permutation routing: n×n Mesh: 7n+o(n) steps; 2n hypercube: O(n2) steps; n×n Torus: 4n+o(n) steps. The algorithm for the two-dimensional grid is the first to be both deterministic and asymptotically optimal. The algorithm for the 2n-nodes Boolean cube is the first deterministic algorithm that achieves a complexity of o(2n) steps |
| |
| Keywords: | |
|
|
