Approximating the minimum-cost maximum flow is P-complete

DOI10.1016/0020-0190(92)90229-OMaRDI QIDQ1198087zbMATH OpenOpenAlexFDO

Authors Clifford Stein, Joel 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

• scientific article; zbMATH DE number 4155879 (Why is no real title available?)
• scientific article; zbMATH DE number 4062587 (Why is no real title available?)
• scientific article; zbMATH DE number 176498 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• Approximating linear programming is log-space complete for P
• The maximum flow problem is log space complete for P

Cited in

(2)

• Complexity and approximability of the maximum flow problem with minimum quantities
• The binary network flow problem is logspace complete for P

This page was built for publication: Approximating the minimum-cost maximum flow is P-complete

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