| Article ID: | iaor20011486 |
| Country: | Netherlands |
| Volume: | 125 |
| Issue: | 2 |
| Start Page Number: | 249 |
| End Page Number: | 256 |
| Publication Date: | Sep 2000 |
| Journal: | European Journal of Operational Research |
| Authors: | Bksi Jzsef, Galambos Gbor, Hajnal Pter |
| Keywords: | Permutation routing |
In this paper we analyze some permutation routing algorithms for different kinds of mesh architectures. First we give lower and upper bounds for the expected number of steps of the basic greedy algorithm on linear and two-dimensional arrays without bus. Finally we present lower bounds for the number of steps of arbitrary on-line or off-line algorithms on rectangular meshes with buses.