Complexity of a classical flow restoration problem

DOI10.1002/net.21508zbMath1338.90084OpenAlexW1970334208WikidataQ113109192 ScholiaQ113109192MaRDI QIDQ2811305

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

Publication date: 10 June 2016

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingmulticommodity flow networkssurvivable network design\(\mathcal{NP}\)-hardnesspath generationequivalence of separation and optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem
• Network synthesis under survivability constraints
• Graph minors. XIII: The disjoint paths problem
• Complexity of column generation in network design with path-based survivability mechanisms
• On the complexity of resilient network design
• Disjoint paths in a network
• Finding k Disjoint Paths in a Directed Planar Graph

This page was built for publication: Complexity of a classical flow restoration problem