Complexity of a classical flow restoration problem

DOI10.1002/NET.21508zbMATH Open1338.90084OpenAlexW1970334208WikidataQ113109192 ScholiaQ113109192MaRDI QIDQ2811305FDOQ2811305

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

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

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)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• The directed subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• Disjoint paths in a network
• Complexity of column generation in network design with path-based survivability mechanisms
• Finding k Disjoint Paths in a Directed Planar Graph
• Title not available (Why is that?)
• The disjoint shortest paths problem
• Network synthesis under survivability constraints
• On the complexity of resilient network design

Cited In (2)

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

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)