A polynomial time solvable concave network flow problem
G. M. Guisewite, Pãnos M. Pardalos · Networks · 1993
Abstract We prove that the single‐source uncapacitated (SSU) version of the concave cost network flow problem, when all arcs except one have linear cost, is in the class P of problems solvable in time polynomial in the problem input length. This contrasts the corresponding result without network constraints, in which the problem is known to be NP‐hard [6]. © 1993 by John Wiley & Sons, Inc.