Minimum flow problem on network flows with time-varying bounds

摘要

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0,1.....T) of time points can be solved by at most n minimum flow computations, by combining of pre-flow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n~2m).