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