Paper Info
Title
A polynomial time algorithm for the minimum flow problem in time-varying networks.
Abstract
Flow variations over time generalize standard network flows by introducing an element of time. In contrast to the classical case of static flows, a flow over time in such a network specifies a flow rate entering an arc for each point in time. In this setting, the capacity of an arc limits the rate of flow into the arc at each point in time. Traditionally, flows over time are computed in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static network flows, its drawback is the enormous size of the time-expanded network. In this paper, we extend the results about the minimum flow problem to network flows (with n nodes and m arcs) in which the time-varying lower bounds can involve both the source and the sink nodes (as in Fathabadi et al.) and also one additional node other than the source and the sink nodes. It is shown that this problem for the set ({0,1,ldots ,T}) of time points can be solved by at most n minimum flow computations, by suitably extending the dynamic minimum flow algorithm and reoptimization techniques. The running time of the presented algorithm is (O(n^2m)).
Year
DOI
Venue
2019
10.1007/s10479-017-2450-2
Annals OR
Keywords
Field
DocType
Network flows, Combinatorial optimization, (Dynamic) Minimum flow, (Dynamic) Preflow-pull algorithm
Push–relabel maximum flow algorithm,Flow network,Mathematical optimization,Out-of-kilter algorithm,Algorithm,Circulation problem,Discrete time and continuous time,Time complexity,Multi-commodity flow problem,Minimum-cost flow problem,Mathematics
Journal
Volume
Issue
ISSN
272
1-2
1572-9338
Citations 
PageRank 
References 
0
0.34
11
Authors
3
Name
Order
Citations
PageRank
Salman Khodayifar122.45
Mohammad Ali Raayatpanah201.35
Panos M. Pardalos314119.60