Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
From MaRDI portal
Publication:1964594
DOI10.1007/s004930050061zbMath0932.68005OpenAlexW3015891365MaRDI QIDQ1964594
Leighton, Tom, Andréa W. Richa, Bruce M. Maggs
Publication date: 21 February 2000
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930050061
Network design and communication in computer systems (68M10) Combinatorial probability (60C05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Mathematical problems of computer architecture (68M07)
Related Items (28)
Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps ⋮ Scheduling trains with small stretch on a unidirectional line ⋮ Direct routing: Algorithms and complexity ⋮ The impact of local policies on the quality of packet routing in paths, trees, and rings ⋮ Atomic routing games on maximum congestion ⋮ Solving the job-shop scheduling problem optimally by dynamic programming ⋮ Scheduling on unrelated machines under tree-like precedence constraints ⋮ Online packet-routing in grids with bounded buffers ⋮ Efficient delay routing ⋮ Scheduling problems in transportation networks of line topology ⋮ A GENERAL PRAM SIMULATION SCHEME FOR CLUSTERED MACHINES ⋮ Oblivious Routing for Sensor Network Topologies ⋮ Scheduling Problems over Network of Machines ⋮ Universal Packet Routing with Arbitrary Bandwidths and Transit Times ⋮ Approximation Algorithms for Generalized Path Scheduling ⋮ Time-optimum packet scheduling for many-to-one routing in wireless sensor networks ⋮ On the benefit of supporting virtual channels in wormhole routers ⋮ [https://portal.mardi4nfdi.de/wiki/Publication:4521547 Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lov�sz local lemma] ⋮ Scheduling problems over a network of machines ⋮ On the power of randomization for job shop scheduling withk-units length tasks ⋮ On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion ⋮ UNIVERSAL ROUTING AND PERFORMANCE ASSURANCE FOR DISTRIBUTED NETWORKS ⋮ Adaptive packet routing for bursty adversarial traffic ⋮ FIFO and randomized competitive packet routing games ⋮ O(log m)-approximation for the routing open shop problem ⋮ Train Scheduling on a Unidirectional Path ⋮ Bounding Residence Times for Atomic Dynamic Routings ⋮ Approximation algorithms for shop scheduling problems with minsum objective
This page was built for publication: Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
