Skip to main content

On the bisection width and expansion of butterfly networks

Publication ,  Journal Article
Bornstein, C; Litman, A; Maggs, BM; Sitaraman, RK; Yatzkar, T
Published in: Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998
January 1, 1998

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(√2-1)n+o(n)≈.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 Ā, provided that k=o(n).

Duke Scholars

Published In

Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998

DOI

Publication Date

January 1, 1998

Volume

1998-March

Start / End Page

144 / 150
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Bornstein, C., Litman, A., Maggs, B. M., Sitaraman, R. K., & Yatzkar, T. (1998). On the bisection width and expansion of butterfly networks. Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998, 1998-March, 144–150. https://doi.org/10.1109/IPPS.1998.669902
Bornstein, C., A. Litman, B. M. Maggs, R. K. Sitaraman, and T. Yatzkar. “On the bisection width and expansion of butterfly networks.” Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998 1998-March (January 1, 1998): 144–50. https://doi.org/10.1109/IPPS.1998.669902.
Bornstein C, Litman A, Maggs BM, Sitaraman RK, Yatzkar T. On the bisection width and expansion of butterfly networks. Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998. 1998 Jan 1;1998-March:144–50.
Bornstein, C., et al. “On the bisection width and expansion of butterfly networks.” Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998, vol. 1998-March, Jan. 1998, pp. 144–50. Scopus, doi:10.1109/IPPS.1998.669902.
Bornstein C, Litman A, Maggs BM, Sitaraman RK, Yatzkar T. On the bisection width and expansion of butterfly networks. Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998. 1998 Jan 1;1998-March:144–150.

Published In

Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998

DOI

Publication Date

January 1, 1998

Volume

1998-March

Start / End Page

144 / 150