Packet routing and job-shop scheduling in O(congestion+dilation) steps
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ó.
Leighton, FT; Maggs, BM; Rao, SB
Volume / Issue
Start / End Page
Electronic International Standard Serial Number (EISSN)
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)