Optimal Oblivious Permutation Routing in Small Hypercubes

Seifert, Thomas and Speckenmeyer, Ewald (1997) Optimal Oblivious Permutation Routing in Small Hypercubes.
Published In: Proceedings of the 4th Workshop on Parallel Systems & Algorithms, PASA '96 : Research Center J├╝lich, Germany, 10 - 12 April 1996 World Scientific 1997, pp. 53-66.


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-2 d' -routing problem and any 2 d' -to-1-routing problem can be solved in at most d' (d' <= 4) communication 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.

Download: [img] Postscript - Preprinted Version
Download (240kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-218
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 09:52
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/218