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

[thumbnail of zpr96-218.pdf]
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: Monograph (['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

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item