de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

#### Improved Routing and Sorting on Multibutterflies

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45673

Vöcking,  Berthold
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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 &lt; 1/4$.