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