next up previous
Next: 1 Introduction

Packet Routing and Job-Shop Scheduling in O(Congestion + Dilation) Steps

F. T. Leighton tex2html_wrap_inline866
Bruce M. Maggs tex2html_wrap_inline868
Satish B. Rao tex2html_wrap_inline870

tex2html_wrap_inline872 Mathematics Department and
Laboratory for Computer Science
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139

tex2html_wrap_inline874 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 tex2html_wrap_inline876 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.

Bruce Maggs
Mon Jul 22 20:27:47 EDT 1996
anonymous logging image