Expanders might be practical: Fast algorithms for routing around faults on multibutterflies
Publication
, Journal Article
Leighton, T; Maggs, B
Published in: Annual Symposium on Foundations of Computer Science (Proceedings)
January 1, 1989
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.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1989
Start / End Page
384 / 389
Citation
APA
Chicago
ICMJE
MLA
NLM
Leighton, T., & Maggs, B. (1989). Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. Annual Symposium on Foundations of Computer Science (Proceedings), 384–389. https://doi.org/10.1109/sfcs.1989.63507
Leighton, T., and B. Maggs. “Expanders might be practical: Fast algorithms for routing around faults on multibutterflies.” Annual Symposium on Foundations of Computer Science (Proceedings), January 1, 1989, 384–89. https://doi.org/10.1109/sfcs.1989.63507.
Leighton T, Maggs B. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. Annual Symposium on Foundations of Computer Science (Proceedings). 1989 Jan 1;384–9.
Leighton, T., and B. Maggs. “Expanders might be practical: Fast algorithms for routing around faults on multibutterflies.” Annual Symposium on Foundations of Computer Science (Proceedings), Jan. 1989, pp. 384–89. Scopus, doi:10.1109/sfcs.1989.63507.
Leighton T, Maggs B. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. Annual Symposium on Foundations of Computer Science (Proceedings). 1989 Jan 1;384–389.
Published In
Annual Symposium on Foundations of Computer Science (Proceedings)
DOI
ISSN
0272-5428
Publication Date
January 1, 1989
Start / End Page
384 / 389