Premium
Incremental flow
Author(s) -
Hartline Jeff,
Sharp Alexa
Publication year - 2007
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.20168
Subject(s) - sequence (biology) , multi commodity flow problem , flow (mathematics) , mathematical optimization , relation (database) , maximum flow problem , mathematics , flow network , time complexity , minimum cost flow problem , computer science , algorithm , data mining , genetics , geometry , biology
This paper defines an incremental version of the maximum flow problem. In this model, the capacities increase over time and the resulting solution is a sequence of flows that build on each other incrementally. Thus far, incremental problems considered in the literature have been built on NP‐complete problems. To the best of our knowledge, our results are the first to find a polynomial time problem whose incremental version is NP‐complete. We present approximation algorithms and hardness results for many versions of this problem, and comment on the relation to multicommodity flow. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 77–85 2007
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom