Approximating the Minimum-Cost Maximum Flow is P-Complete.

Clifford Stein Joel Wein

Published in: Inf. Process. Lett. (1992)

Keyphrases

minimum cost
maximum flow
np hard
minimum cut
approximation algorithms
network flow
network flow problem
capacity constraints
spanning tree
directed graph
network simplex algorithm
push relabel
minimum cost flow
flow network
min cut max flow
similarity measure
branch and bound