• 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. 144-150.

  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) (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.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page