Almost optimal permutation routing on hypercubes
Berthold Vöcking · 2001
This paper deals with permutation routing on hypercube networks in the store-and-forward model. We introduce the first (on-line and off-line) algorithms routing any permutation on the d-dimensional hypercube in d+o(d) steps. The best previously known results were 2d+o(d) (oblivious on-line) and 2d-3 (off-line). In particular, we present