On a capacity scaling algorithm for the constrained maximum flow problem
Cenk Çalışkan · Networks · 2008
Abstract 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. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009