Journal of the ACM Bibliography

Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.3 [Probability and Statistics]

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Multi-port, packet routing, permutation routing, randomized routing algorithms, single-port

Selected papers that cite this one

• Miltos D. Grammatikakis, D. Frank Hsu, and Jop F. Sibeyn. Packet routing in fixed-connection networks: A survey. Journal of Parallel and Distributed Computing, 54(2):77-132, 1 November 1998.

Selected references

• William A. Aiello, F. T. Leighton, Bruce M. Maggs, and Mark Newman. Fast algorithms for bit-serial routing on a hypercube. Mathematical Systems Theory, 24(4):253-271, 1991.

• Romas Aleliunas. Randomized parallel communication (preliminary version). In ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 60-72, Ottawa, Canada, 18-20 August 1982.

• A. Borodin and J. E. Hopcroft. Routing, merging, and sorting on parallel models of computation. Journal of Computer and System Sciences, 30(1):130-145, February 1985.

• Allan Borodin, Prabhakar Raghavan, Baruch Schieber, and Eli Upfal. How much can hardware help routing? (extended abstract). In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 573-582, San Diego, California, 16-18 May 1993.

• Christos Kaklamanis, Danny Krizanc, and Thanasis Tsantilas. Tight bounds for oblivious routing in the hypercube. Mathematical Systems Theory, 24(4):223-232, 1991.

• Tom Leighton and Bruce Maggs. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. In 30th Annual Symposium on Foundations of Computer Science, pages 384-389, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM Journal on Computing, 18(4):740-747, August 1989.

• Eli Upfal. Efficient schemes for parallel communication. Journal of the ACM, 31(3):507-517, July 1984.

• Eli Upfal. An O(log N) deterministic packet-routing scheme. Journal of the ACM, 39(1):55-70, January 1992.

• L. G. Valiant and G. J. Brebner. Universal schemes for parallel communication. In Conference Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computation, pages 263-277, Milwaukee, Wisconsin, 11-13 May 1981.

• Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). In 18th Annual Symposium on Foundations of Computer Science, pages 222-227, Providence, Rhode Island, 31 October-2 November 1977. IEEE.

Shortcuts: