@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c",
center "@c",
right "@c")
@heading(Improved Routing and Sorting on Multibutterflies)
@heading(CMU-CS-96-192)
@center(@b(Bruce M. Maggs, Berthold Vocking@foot))
@center(November 1996)
@center(FTP: CMU-CS-96-192.ps)
@blankspace(1)
@begin(text)
This paper shows that an @math-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
keys on an @math-input multibutterfly in @math time, a
work-efficient algorithm for finding the median of
@math
keys on an @math-input multibutterfly in @math time,
and a three-dimensional VLSI layout for the @math-input AKS network with
volume @math. 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 relations on an @math-input multibutterfly
in @math time. Previously, only algorithms for solving
@math 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
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(21 pages)])