# Technical Report CS0908

 TR#: CS0908 Class: CS Title: On the Bisection Width and Expansion of Butterfly Networks Authors: Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman and Tal Yatzkar PDF CS0908.pdf Abstract: This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an $n$-input butterfly network is $2(\sqrt{2}-1)n + o(n) \approx .82n$ without wraparound, and $n$ with wraparound. The former result is surprising, since it contradicts the prior folklore'' belief that the bisection width was $n$. We also show that every set of $k$ nodes has at least $k / (2 \cdot \log k)$ neighbors in a butterfly without wraparound, and at least $k / \log k$ neighbors in a butterfly with wraparound, if $k$ is $o(\sqrt{n})$ and $o(n)$ respectively. Copyright The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CS/CS0908), rather than to the URL of the PDF files directly. The latter URLs may change without notice.