%0 Journal Article %1 DBLP:journals/combinatorica/LeightonMR94 %A Leighton, Frank Thomson %A Maggs, Bruce M. %A Rao, Satish %D 1994 %J Combinatorica %K linear_programming power_consumption santa.claus.problem scheduling %N 2 %P 167-186 %R 10.1007/BF01215349 %T Packet Routing and Job-Shop Scheduling in (Congestion + Dilation) Steps %V 14 %X 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.

@article{DBLP:journals/combinatorica/LeightonMR94, 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.}, added-at = {2009-10-11T06:03:49.000+0200}, author = {Leighton, Frank Thomson and Maggs, Bruce M. and Rao, Satish}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/2ad2f56726b503e7578534d4601f547e6/ytyoun}, doi = {10.1007/BF01215349}, interhash = {d2f3b859ab50a2b5d6d56b217977b880}, intrahash = {ad2f56726b503e7578534d4601f547e6}, journal = {Combinatorica}, keywords = {linear_programming power_consumption santa.claus.problem scheduling}, number = 2, pages = {167-186}, timestamp = {2016-06-14T13:16:57.000+0200}, title = {Packet Routing and Job-Shop Scheduling in {\it }(Congestion + Dilation) Steps}, volume = 14, year = 1994 }