Fast algorithms for finding O(congestion+dilation) packet routing schedules
- 19 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Leighton, Maggs and Rao (1988) 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 dilation). The proof, however, used the Lova/spl acute/sz (1975) local lemma and was not constructive. In this paper, we show how to find such a schedule in O(NE+Elog/sup /spl epsiv//E) time, for any fixed /spl epsiv/Keywords
This publication has 10 references indexed in Scilit:
- Randomized Routing and Sorting on Fixed-Connection NetworksJournal of Algorithms, 1994
- Packet routing and job-shop scheduling inO(congestion+dilation) stepsCombinatorica, 1994
- Greedy Packet Scheduling on Shortest PathsJournal of Algorithms, 1993
- Methods for message routing in parallel machinesPublished by Association for Computing Machinery (ACM) ,1992
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- An algorithmic approach to the Lovász local lemma. IRandom Structures & Algorithms, 1991
- Work-preserving emulations of fixed-connection networksPublished by Association for Computing Machinery (ACM) ,1989
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952