Packet routing and job-shop scheduling in O(congestion+dilation) steps


Journal Article

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

Full Text

Duke Authors

Cited Authors

  • Leighton, FT; Maggs, BM; Rao, SB

Published Date

  • June 1, 1994

Published In

Volume / Issue

  • 14 / 2

Start / End Page

  • 167 - 186

Electronic International Standard Serial Number (EISSN)

  • 1439-6912

International Standard Serial Number (ISSN)

  • 0209-9683

Digital Object Identifier (DOI)

  • 10.1007/BF01215349

Citation Source

  • Scopus