Complexity and approximability of the maximum flow problem with minimum quantities

DOI10.1002/NET.21502zbMATH Open1338.68119DBLPjournals/networks/ThielenW13OpenAlexW2071026504WikidataQ57851375 ScholiaQ57851375MaRDI QIDQ2811300FDOQ2811300

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

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

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)

Cites Work

• Title not available (Why is that?)
• Minimum cost flows with minimum quantities
• Minimal-cost network flow problems with variable lower bounds on arc flows
• The Recognition of Series Parallel Digraphs
• Erratum to ``Minimum cost flows with minimum quantities

Cited In (12)

• 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
• On one maximum multiflow problem and related metrics
• Title not available (Why is that?)
• Erratum to ``Minimum cost flows with minimum quantities
• Title not available (Why is that?)
• Minimum cost flows with minimum quantities
• Resource loading with time windows
• Complexity of a classical flow restoration problem
• NP-COMPLETENESS AND APPROXIMATION ALGORITHM FOR THE MAXIMUM INTEGRAL VERTEX-BALANCED FLOW PROBLEM
• The maximum residual flow problem: NP‐hardness with two‐arc destruction
• Title not available (Why is that?)

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)