**F. T. Leighton
Bruce M. Maggs
Satish B. Rao
Mathematics Department and
Laboratory for Computer Science
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139
NEC Research Institute
4 Independence Way
Princeton, NJ 08540**

*In this paper, we prove that there exists a schedule
for routing any set of packets with edge-simple paths, on any network,
in steps, where c is the congestion of the paths in the
network, and d is the length of the longest path. The result has
applications to packet routing in parallel machines, network
emulations, and job-shop scheduling. *

- 1 Introduction
- 2 An on-line algorithm
- 3 An O(c+d)-step schedule
- 4 Counterexamples to on-line algorithms
- 5 Acknowledgements
- References
- About this document ...

Mon Jul 22 20:27:47 EDT 1996