On the Hot-Potato Permutation Routing Algorithm of Borodin, Rabani and Schieber

Richard Thomas Plunkett
Basser Department of Computer Science, University of Sydney, NSW 2006, Australia.
richard@cs.su.oz.au

Antonis Symvonis
Basser Department of Computer Science, University of Sydney, NSW 2006, Australia.
symvonis@cs.su.oz.au

Abstract

Borodin, Rabani and Schieber presented an $O(n \sqrt n)$-step algorithm for hot-potato routing of permutations on $n \times n$ meshes. They conjectured that their algorithm completes the routing of a permutation in O(n) steps. In this paper, we present worst-case partial permutations which force their algorithm to use $\Omega (n \sqrt n)$ routing steps.

Conference Home Page