Abstract
New deterministic algorithms for routing permutations on two-dimensional meshes are developed. On an n × n array, one algorithm runs in the optimal 2 · n - 2 steps, with maximum queue length 32. Another algorithm runs in near-optimal time, 2 · n + script O sign(1) steps, with a maximum queue length of only 12.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 111-141 |
| Number of pages | 31 |
| Journal | Journal of Algorithms |
| Volume | 22 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1997 |
| Externally published | Yes |
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics