zbMATH — the first resource for mathematics

On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks. (English) Zbl 1379.68013
Mayr, Ernst W. (ed.) et al., STACS 95. 12th annual symposium on theoretical aspects of computer science, Munich, Germany, March 2–4, 1995. Proceedings. Berlin: Springer-Verlag (ISBN 3-540-59042-0). Lecture Notes in Computer Science 900, 255-266 (1995).
Summary: The sizes of permutation networks for special sets of permutations are investigated. The study of the planar realization and the search for small but hard sets of permutations are also included. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here.
The two main results are:
(i) an asymptotically optimal permutation network of size \(6\cdot N \cdot \log\log N\) for shifts of power 2.
(ii) an asymptotically optimal planar permutation network of size \(\Theta(N^2\cdot(\log\log N/\log N)^2)\) for shifts of power 2.
A consequence of our results is a construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one step in \(O(\log\log N)\) communication steps. A new sorting network as well as an essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follow.
For the entire collection see [Zbl 0813.68028].

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI