Packet Routing: Complexity and Algorithms

DOI10.1007/978-3-642-12450-1_20MaRDI QIDQ3558928zbMATH OpenOpenAlexFDO

Authors Britta Peis, Andreas Wiese, Martin Skutella

Publication date 11 May 2010

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.919.7335

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Routing optimization in packet switching communication networks
• Direct routing: Algorithms and complexity
• Algorithms – ESA 2004
• scientific article; zbMATH DE number 1538069
• Optimal packet fragmentation and routing in computer networks
• Packet routing in fixed-connection networks: A survey
• On the complexity of quality of service routing
• The generalized packet routing problem
• Internet packet routing: application of a K-quickest path algorithm

Cited in

(29)

• Efficient delay routing
• Fast algorithms for finding \(O\)(Congestion+Dilation) packet routing schedules
• Multiple train repositioning operations in a railyard network
• Scheduling problems over a network of machines
• Direct routing: Algorithms and complexity
• Routing equal-size messages on a slotted ring
• A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
• On the complexity of quality of service routing
• Universal packet routing with arbitrary bandwidths and transit times
• Policies for periodic packet routing
• Throughput maximization for periodic packet routing on trees and grids
• Some complexity results about packet radio networks (Corresp.)
• Packet Routing on the Grid
• scientific article; zbMATH DE number 1559579 (Why is no real title available?)
• scientific article; zbMATH DE number 2090665 (Why is no real title available?)
• OPTIMUM SCHEDULE PROBLEMS IN STORE AND FORWARD NETWORKS
• Package routing in transportation networks with fixed vehicle schedules
• Computational complexity of convoy movement planning problems
• Scheduling problems over network of machines
• Train scheduling on a unidirectional path
• Efficient offline algorithmic techniques for several packet routing problems in distributed systems
• Optimal Node Routing
• Algorithms – ESA 2004
• The generalized packet routing problem
• Bounding Residence Times for Atomic Dynamic Routings
• Two exact algorithms for the packet scheduling problem
• Network routing on regular digraphs and their line graphs
• Near-optimal schedules for simultaneous multicasts
• Scheduling trains with small stretch on a unidirectional line

This page was built for publication: Packet Routing: Complexity and Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3558928)