Packet routing and job-shop scheduling inO(congestion+dilation) steps Export

@article{citeulike:1775099, abstract = {In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, inO(c+d) steps, wherec is the congestion of the paths in the network, andd is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling.}, author = {Leighton, F. T. and Maggs, Bruce M. and Rao, Satish B.}, citeulike-article-id = {1775099}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF01215349}, day = {21}, doi = {10.1007/BF01215349}, journal = {Combinatorica}, keywords = {interesting, online\_algorithms, routing}, month = {June}, number = {2}, pages = {167--186}, posted-at = {2007-10-16 16:48:30}, priority = {2}, title = {Packet routing and job-shop scheduling inO(congestion+dilation) steps}, url = {http://dx.doi.org/10.1007/BF01215349}, volume = {14}, year = {1994} }

TY - JOUR ID - citeulike:1775099 L3 - citeulike-article-id:1775099 N2 - In this paper, we prove that there exists a schedule for routing any set of packets with edge-simple paths, on any network, inO(c+d) steps, wherec is the congestion of the paths in the network, andd is the length of the longest path. The result has applications to packet routing in parallel machines, network emulations, and job-shop scheduling. IS - 2 JF - Combinatorica EP - 186 TI - Packet routing and job-shop scheduling inO(congestion+dilation) steps VL - 14 SP - 167 KW - interesting KW - online_algorithms KW - routing AU - Leighton, FT AU - Maggs, Bruce AU - Rao, Satish PY - 1994/06/21/ UR - http://dx.doi.org/10.1007/BF01215349 ER -