Convex generalized flows

DOI10.1016/j.dam.2015.03.021zbMath1316.05054OpenAlexW296286681MaRDI QIDQ2352786

Sven O. Krumke, Michael Holzhauser, Clemens Thielen

Publication date: 6 July 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.03.021

zbMATH Keywords

computational complexitygeneralized flowsflow decompositionmaximum flowsnetwork flow algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization.
• An \(\varepsilon\)-relaxation method for separable convex cost generalized network flow problems
• Dioïds and semirings: Links to fuzzy sets and other applications
• Generalized max flow in series-parallel graphs
• Maximum network flows with concave gains
• Combinatorial Algorithms for the Generalized Circulation Problem
• New Methods in Mathematical Programming—Optimal Flow Through Networks with Gains
• The Recognition of Series Parallel Digraphs
• On Max Flows with Gains and Pure Min-Cost Flows
• Optimal flows in nonlinear gain networks
• Graph Classes: A Survey
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines