Approximating the minimum-cost maximum flow is P-complete

DOI10.1016/0020-0190(92)90229-OzbMath0772.68056OpenAlexW1969990079MaRDI QIDQ1198087

Clifford Stein, Joel M. Wein

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90229-o

zbMATH Keywords

maximum flowminimum-cost flow\(P\)-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Cites Work

• Approximating linear programming is log-space complete for P
• The maximum flow problem is log space complete for P
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item