On the bisection width and expansion of butterfly networks
Claudson Ferreira Bornstein, Ami Litman, Bruce MacDowell Maggs, Ramesh K. Sitaraman, T. Yatzkar · 2002
The paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. Previously it was known that the bisection width of an n-input butterfly with wraparound is n. We show that without wraparound, the bisection width is 2(/spl radic/2-1)n+o(n)/spl ap/.82 n. This result is surprising because it contradicts the prior "folklore" belief that the bisection width is n in both cases. We also show that for every set A of k nodes in a butterfly with wraparound there are at least (4+o(1))k/log k edges from A to A, provided that k=o(n).