Publications [#236677] of Bruce Maggs

Journal articles or Book chapters PUBLISHED

1. Leighton, T; Maggs, B, Expanders might be practical: Fast algorithms for routing around faults on multibutterflies, Annual Symposium on Foundations of Computer Science (Proceedings) (January, 1989), pp. 384-389 [doi]
   (last updated on 2024/04/24)

   Abstract:
   Simple deterministic O(log N)-step algorithms for routing packets on a multibutterfly are described. The algorithms are shown to be robust against faults, even in the worst case, and to be efficient from a practical point of view. As a consequence, the multibutterfly is shown to be an excellent candidate for a high-bandwidth, low-diameter switching network underlying a distributed-memory machine.