On the complexity of resilient network design

DOI10.1002/NET.20321MaRDI QIDQ3057137zbMATH OpenOpenAlexFDO

Authors 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 flowsnetwork optimizationNP-hardnessresilient networks

Mathematics Subject Classification ID

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

Recommendations

• Hardness of robust network design
• Optimizing network topology for cascade resilience
• scientific article; zbMATH DE number 795223
• Design of survivable networks
• Design of survivable networks with vulnerability constraints
• On the approximability of robust network design
• scientific article; zbMATH DE number 1717222
• Approximability of robust network design

Cites work

• Disjoint paths in a network
• scientific article; zbMATH DE number 3858857 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Network synthesis under survivability constraints
• On the hardness of approximating minimization problems
• Reserving resilient capacity in a network
• Shortest Path Problems with Resource Constraints
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(14)

• On interdependent failure resilient multi-path routing in smart grid communication network
• The complexity of reconfiguring network models
• On multi-path routing for reliable communications in failure interdependent complex networks
• Designing networks with resiliency to edge failures using two-stage robust optimization
• Reserving resilient capacity in a network
• scientific article; zbMATH DE number 1717222 (Why is no real title available?)
• Complexity of a classical flow restoration problem
• Complexity of column generation in network design with path-based survivability mechanisms
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Optimizing flow thinning protection in multicommodity networks with variable link capacity
• Resilience of communication networks to random failures and disasters: An optimization perspective
• A robust optimization model for affine/quadratic flow thinning: A traffic protection mechanism for networks with variable link capacity
• On designing networks resilient to clique blockers
• Building edge-failure resilient networks

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

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