On the complexity of resilient network design

DOI10.1002/net.20321zbMath1200.90035OpenAlexW4253619081MaRDI QIDQ3057137

Artur Tomaszewski, Michał Pióro, Mateusz Żotkiewicz

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20321

zbMATH Keywords

multicommodity flowsNP-hardnessnetwork optimizationresilient networks

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Complexity of column generation in network design with path-based survivability mechanisms ⋮ A robust optimization model for affine/quadratic flow thinning: A traffic protection mechanism for networks with variable link capacity ⋮ Optimizing Flow Thinning Protection in Multicommodity Networks with Variable Link Capacity ⋮ Complexity of a classical flow restoration problem ⋮ Designing networks with resiliency to edge failures using two-stage robust optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Network synthesis under survivability constraints
• Reserving Resilient Capacity in a Network
• Disjoint paths in a network
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• On the hardness of approximating minimization problems
• Shortest Path Problems with Resource Constraints

This page was built for publication: On the complexity of resilient network design