Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm

Dorit S. Hochbaum

We explore here surprising links between the time-cost-tradeoff problem and the minimum cost flow problem that lead to fast, strongly polynomial, algorithms for both problems. One…