- Fast algorithms for finding O(congestion+dilation) packet
routing schedules. F. T. Leighton, B. M. Maggs, and A. W. Richa,
Combinatorica, Volume 19, Number 3, 1999, pp. 375-401.
- In 1988, Leighton, Maggs, and Rao showed that for any network
and any set of packets whose paths through the network are fixed and
edge-simple, there exists a schedule for routing the packets to their
destinations in O(c+d) steps using constant-size queues, where c is
the congestion of the paths in the network, and d is the length of the
longest path. The proof, however, used the Lovasz Local Lemma and was
not constructive. In this paper, we show how to find such a schedule
in O(P(loglog P)log P) time, with probability 1-1/P^b, for any
positive constant b, where P is the sum of the lengths of the paths
taken by the packets in the network. We also show how to parallelize
the algorithm so that it runs in NC. The method that we use to
construct the schedules is based on the algorithmic form of the Lovasz
Local Lemma discovered by Beck.

**Back to other
publications**

**Back to my home page**