next up previous
Next: About this document Up: Packet Routing and Job-Shop Previous: 5 Acknowledgements


N. Alon. A parallel algorithmic version of the Local Lemma. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, pages 586-593, 1991.

J. Beck. An algorithmic approach to the Lovász Local Lemma I. Random Structures and Algorithms.

R. Koch, T. Leighton, B. Maggs, S. Rao, and A. Rosenberg. Work-preserving emulations of fixed-connection networks. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 227-240, May 1989.

E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. Technical Report BS-R8909, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands, June 1989.

F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays tex2html_wrap_inline2316 Trees tex2html_wrap_inline2318 Hypercubes. Morgan Kaufmann, San Mateo, CA, 1992.

F. T. Leighton, B. M. Maggs, A. G. Ranade, and S. B. Rao. Randomized routing and sorting on fixed-connection networks. Journal of Algorithms. To appear.

T. Leighton, B. Maggs, and S. Rao. Fast algorithms for finding O(congestion + dilation) packet routing schedules. Manuscript in preparation.

T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 256-271. IEEE Computer Society Press, October 1988.

A. G. Ranade. How to emulate shared memory. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 185-194. IEEE Computer Society Press, October 1987.

S. V. Sevast'yanov. Bounding algorithm for routing problem with arbitrary paths and alternate servers. Kibernetika, 22(6):74-79, 1986. Translation in Cybernetics 22, pages 773-780.

D. B. Shmoys, C. Stein, and J. Wein. Improved approximation algorithms for shop scheduling problems. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 148-157, January 1991.

J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Philadelphia, PA, 1987.

Bruce Maggs
Mon Jul 22 20:27:47 EDT 1996