Complexity of a classical flow restoration problem

DOI10.1002/NET.21508MaRDI QIDQ2811305zbMATHOpenAlexWikidataFDO

Authors Dritan Nace, Michał Pióro, Artur Tomaszewski, 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 programmingsurvivable network design\(\mathcal{NP}\)-hardnesspath generationequivalence of separation and optimizationmulticommodity flow networks

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3950169
• The complexity of computing a robust flow
• Complexity analysis for maximum flow problems with arc reversals
• Complexity and approximability of the maximum flow problem with minimum quantities
• Algorithms and complexity analysis for some flow problems
• On the complexity of the flow coloring problem
• scientific article; zbMATH DE number 4123497
• scientific article; zbMATH DE number 4093147
• scientific article; zbMATH DE number 1418332
• scientific article; zbMATH DE number 4055051

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5070513 (Why is no real title available?)
• Complexity of column generation in network design with path-based survivability mechanisms
• Disjoint paths in a network
• Finding k Disjoint Paths in a Directed Planar Graph
• Graph minors. XIII: The disjoint paths problem
• Network flows. Theory, algorithms, and applications.
• Network synthesis under survivability constraints
• On the complexity of resilient network design
• The directed subgraph homeomorphism problem
• The disjoint shortest paths problem

Cited in

(2)

• Existence of a classical solution to complex material flow problems
• The maximum residual flow problem: NP‐hardness with two‐arc destruction

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

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