Name
Abstract | ||
|---|---|---|
This 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)驴 .82n. 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). |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1007/s00224-001-1026-2 | Theory of Computing Systems |
Keywords | DocType | Volume |
Output Node,Output Port,Input Port,Input Node,Total Unit | Conference | 34 |
Issue | ISSN | ISBN |
6 | 1433-0490 | 0-8186-8404-6 |
Citations | PageRank | References |
9 | 0.61 | 17 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Claudson F. Bornstein | 1 | 110 | 10.93 |
| Ami Litman | 2 | 240 | 49.78 |
| Bruce M. Maggs | 3 | 3592 | 368.31 |
| Ramesh K. Sitaraman | 4 | 1928 | 141.68 |
| Tal Yatzkar | 5 | 9 | 0.61 |