"Optimal Oblivious Permutation Routing in Small Hypercubes"
Article by Thomas Seifert, Ewald Speckenmeyer, available as BibTeX Source, postscript file and compressed postscript file.
Informatik, Universität zu Köln
Preprint Key:	zpr96-218
Keywords:	hypercubes, oblivious routing, permutations, routing
MSC codes:	94C99
This article was published in 1997 by World Scientific in the proceedings "Proc. of the 4th Workshop on Parallel Systems and Algorithms (PASA '96)" (edited by F. Hoss;feld, E. Maehle, E. W. Mayer), number 218, pages 53--66.
Abstract:	For each d <= 8 we provide an oblivious algorithm for routing any permutation on the d-dimensional hypercube in at most d communication steps. To prove our result we show that any 1-to-2d'-routing problem and any 2d'-to-1-routing problem can be solved in at most d' (d' <= 4) coummunication steps on a d'-dimensional hypercube. Furthermore we present a class of efficiently working routing algorithms which allows us to make an improved statement about the complexity of some of the provided algorithms.