Almost optimal permutation routing on hypercubes

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 2 d+o(d) (oblivious on-line) and 2 d -3 (off-line). In particular, we present

Authors

• Berthold Vöcking

Keywords

No keywords are indexed for this paper.