Packet routing and job-shop scheduling in O(congestion+dilation) steps
Publication
, Journal Article
Leighton, FT; Maggs, BM; Rao, SB
Published in: Combinatorica
June 1, 1994
In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, in O(c+d) 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. © 1994 Akadémiai Kiadó.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Combinatorica
DOI
EISSN
1439-6912
ISSN
0209-9683
Publication Date
June 1, 1994
Volume
14
Issue
2
Start / End Page
167 / 186
Related Subject Headings
- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 08 Information and Computing Sciences
- 01 Mathematical Sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Leighton, F. T., Maggs, B. M., & Rao, S. B. (1994). Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica, 14(2), 167–186. https://doi.org/10.1007/BF01215349
Leighton, F. T., B. M. Maggs, and S. B. Rao. “Packet routing and job-shop scheduling in O(congestion+dilation) steps.” Combinatorica 14, no. 2 (June 1, 1994): 167–86. https://doi.org/10.1007/BF01215349.
Leighton FT, Maggs BM, Rao SB. Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica. 1994 Jun 1;14(2):167–86.
Leighton, F. T., et al. “Packet routing and job-shop scheduling in O(congestion+dilation) steps.” Combinatorica, vol. 14, no. 2, June 1994, pp. 167–86. Scopus, doi:10.1007/BF01215349.
Leighton FT, Maggs BM, Rao SB. Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica. 1994 Jun 1;14(2):167–186.
Published In
Combinatorica
DOI
EISSN
1439-6912
ISSN
0209-9683
Publication Date
June 1, 1994
Volume
14
Issue
2
Start / End Page
167 / 186
Related Subject Headings
- Computation Theory & Mathematics
- 49 Mathematical sciences
- 46 Information and computing sciences
- 08 Information and Computing Sciences
- 01 Mathematical Sciences