 On the Bisection Width and Expansion of
Butterfly Networks. C. F. Bornstein, A. Litman, B. M. Maggs,
R. K. Sitaraman, and T. Yatzkar. Proceedings of the 12th International
Parallel Processing Symposium (IPPS), March 1998, pp. 144150.

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 ninput butterfly network is 2(sqrt{2}1)n +
o(n) (approximately .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 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.
 Back to other
publications
 Back to my home page