• Packet routing and job-shop scheduling in O(congestion+dilation) steps. F. T. Leighton, B. M. Maggs, and S. B. Rao, Combinatorica, Vol. 14, No. 2, 1994, pp. 167-180.

  This paper shows that for any network and any set of packets whose paths through the network are fixed, there exists a schedule for routing the packets to their destinations in O(c+d) steps, where c is the congestion of the paths, and d is the dilation. One of the main applications of this result is that if a guest network can be embedded in a host network with load l, congestion c, and dilation d, then the host can emulate the guest with O(l+c+d) slowdown.

  HTML Postscript Compressed Postscript
  Back to other publications

  Back to my home page