Technical Report CS0908

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
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.
CopyrightThe 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 (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion