On a Capacity Scaling Algorithm for the Constrained Maximum Flow Problem
Ahuja and Orlin (Networks 25 (1995), 89-98) introduced a constrained maximum flow problem and proposed its first polynomial combinatorial algorithm. The problem has important applications and is related to important problems such as the knapsack problem. In this article, we show that the algorithm may not terminate with a feasible solution in certain instances and provide a modified version with the same complexity. (C) 2008 Wiley Periodicals, Inc. NETWORKS, Vol. 53(3), 229-230 2009
capacity scaling maximum flow minimum cost network flow polynomial algorithm