- Improved routing and sorting on multibutterflies.
B. M. Maggs and B. Voecking. Algorithmica, Volume 28, Number 4,
2000, pp. 438-464.
- This paper shows that an N-node AKS network (as described by
Paterson) can be embedded in a (3N/2)-node degree-8
multibutterfly network with load 1, congestion 1, and dilation 2. The
result has several implications, including the first deterministic
algorithms for sorting and finding the median of n log n keys on an
n-input multibutterfly in O(log n) time, a work-efficient
algorithm for finding the median of n (log^2 n) log log n keys on an
n-input multibutterfly in O(log n (loglog n) time, and a
three-dimensional VLSI layout for the n-input AKS network with
volume O(n^{3/2}). While these algorithms are not practical, they
provide further evidence of the robustness of multibutterfly networks.
We also present a separate, and more practical, deterministic
algorithm for routing h relations on an n-input multibutterfly in
O(h + log n) time. Previously, only algorithms for solving h
one-to-one routing problems were known. Finally, we show that a
2-folded butterfly, whose individual splitters do not exhibit
expansion, can emulate a bounded-degree multibutterfly with an
(alpha,beta) expansion property, for any alpha * beta < 1/4.

**Back to other
publications**

**Back to my home page**