Publications [#236688] of Bruce Maggs

Journal articles or Book chapters PUBLISHED

1. Leighton, FT; Maggs, BM; Rao, SB, Packet routing and job-shop scheduling in O(congestion+dilation) steps, Combinatorica, vol. 14 no. 2 (June, 1994), pp. 167-186, Springer Nature, ISSN 0209-9683 [doi]
   (last updated on 2024/04/18)

   Abstract:
   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ó.