Premium
A polynomial time solvable concave network flow problem
Author(s) -
Guisewite G. M.,
Pardalos P. M.
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230208
Subject(s) - flow network , time complexity , minimum cost flow problem , flow (mathematics) , class (philosophy) , polynomial , multi commodity flow problem , mathematics , mathematical optimization , maximum flow problem , combinatorics , computer science , discrete mathematics , artificial intelligence , mathematical analysis , geometry
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.