Dynamic vs. oblivious routing in network design

DOI10.1007/s00453-010-9455-4zbMath1221.68037arXiv1309.4140OpenAlexW2105667010MaRDI QIDQ634684

Navin Goyal, Neil Olver, F. Bruce Shepherd

Publication date: 16 August 2011

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.4140

zbMATH Keywords

oblivious routingrobust network designdynamic routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The robust network loading problem with dynamic routing ⋮ Affine recourse for the robust network design problem: Between static and dynamic routing ⋮ Randomized oblivious integral routing for minimizing power cost ⋮ Static and dynamic routing under disjoint dominant extreme demands ⋮ A comparison of routing sets for robust network design ⋮ On the approximability of robust network design ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual algorithms for connected facility location problems
• On-line routing in all-optical networks
• Approximation via cost sharing
• Hardness of robust network design
• Designing Least-Cost Nonblocking Broadband Networks
• Oblivious routing on node-capacitated and directed graphs
• Provisioning a virtual private network
• A tight bound on approximating arbitrary metrics by tree metrics