A polynomial time solvable concave network flow problem | Zendy

Guisewite G. M. | Zendy; Pardalos P. M. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research