Complexity and approximability of the maximum flow problem with minimum quantities

DOI10.1002/NET.21502MaRDI QIDQ2811300zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Clemens Thielen, Stephan Westphal

Publication date 10 June 2016

Published in Networks (Search for Journal in Brave)

Full work available at URL http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:hbz:386-kluedo-31819

zbMATH Keywords

computational complexityapproximation algorithmsmaximum flow problemminimum quantities

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Flows in graphs (05C21)

Recommendations

• On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
• Algorithms and complexity for the almost equal maximum flow problem
• Approximating the minimum-cost maximum flow is P-complete
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• The complexity of minimum cut and maximum flow problems in an acyclic network
• Minimum maximal flow problem: An optimization over the efficient set
• A mixed integer programming approach for the minimum maximal flow
• An Approximation for a Continuous Max-Flow Problem
• scientific article; zbMATH DE number 3950169

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Erratum to ``Minimum cost flows with minimum quantities
• Minimal-cost network flow problems with variable lower bounds on arc flows
• Minimum cost flows with minimum quantities
• The Recognition of Series Parallel Digraphs

Cited in

(16)

• On the Complexity of Computing Maximum and Minimum Min‐Cost‐Flows
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Exponential Space Complexity for Symbolic Maximum Flow Algorithms in 0-1 Networks
• Algorithms and complexity for the almost equal maximum flow problem
• On one maximum multiflow problem and related metrics
• Erratum to ``Minimum cost flows with minimum quantities
• scientific article; zbMATH DE number 150473 (Why is no real title available?)
• Minimum cost flows with minimum quantities
• Resource loading with time windows
• NP-COMPLETENESS AND APPROXIMATION ALGORITHM FOR THE MAXIMUM INTEGRAL VERTEX-BALANCED FLOW PROBLEM
• Complexity of a classical flow restoration problem
• Parallel algorithms for the maximum flow problem with minimum lot sizes
• Algorithms and complexity for the almost equal maximum flow problem
• The maximum residual flow problem: NP‐hardness with two‐arc destruction
• Computing kernels in parallel: lower and upper bounds
• scientific article; zbMATH DE number 6402605 (Why is no real title available?)

This page was built for publication: Complexity and approximability of the maximum flow problem with minimum quantities

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