# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Improved Routing and Sorting on Multibutterflies

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Maggs, B. M., & Vöcking, B. (2000). Improved Routing and Sorting on Multibutterflies.* Algorithmica,* *28*(4), 438-464. Retrieved from http://link.springer.de/link/service/journals/00453/contents/00/10049/paper/10049.pdf.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-33C3-4

##### Abstract

This paper shows that an $N$-node AKS network (as described by Paterson) can be
embedded in a
$\frac{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 deterministic algorithm for
finding the median of $n \log^2 n \log\log n$ keys on an $n$-input
multibutterfly in $O(\log n \log\log 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
$(\alpha,\beta)$-expansion, for any
$\alpha \cdot \beta < 1/4$.