- 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.
- Back to other
- Back to my home page