Universität zu Köln

Seifert, Thomas and Speckenmeyer, Ewald (1997). Optimal Oblivious Permutation Routing in Small Hypercubes. World Scientific. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr96-218.pdf - Draft Version Download (216kB) | Preview

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-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.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Seifert, Thomas UNSPECIFIED UNSPECIFIED UNSPECIFIED Speckenmeyer, Ewald UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547051
Page Range:	pp. 53-66
Date:	1997
Publisher:	World Scientific
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54705