@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Improved Routing and Sorting on Multibutterflies)
@heading(CMU-CS-96-192)
@center(@b(Bruce M. Maggs, Berthold Vocking@foot<Department of Mathematics and Computer Science, and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany.>))
@center(November 1996)
@center(FTP: CMU-CS-96-192.ps)
@blankspace(1)
@begin(text)

This paper shows that an @math<N>-node AKS network (as described by
Paterson) can be embedded in a @math<@smallfraction(Num"3N", Denom "2"XF)#@sub#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 @math<n##log##n>
keys on an @math<n>-input multibutterfly in @math<O(log#n)> time, a
work-efficient algorithm for finding the median of 
@math<n#log@+{2}#n#log#log#n>
keys on an @math<n>-input multibutterfly in @math<O(log#n#log#log#n)> time,
and a three-dimensional VLSI layout for the @math<n>-input AKS network with
volume @math<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 @math<h> relations on an @math<n>-input multibutterfly
in @math<O(h#@add#log#n)> time.  Previously, only algorithms for solving 
@math<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
@math<(@g{a},#@g{b})> expansion property, for any @math<@g{a}#:#@g{b}#@lt#1/4>.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Multibutterfly networks, AKS sorting network, routing 
algorithms, sorting algorithms>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(21 pages)])