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

approximation algorithmscomputational complexitymaximum flow problemminimum quantities

Mathematics Subject Classification ID

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

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

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

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)