A polynomial time algorithm for the minimum flow problem in time-varying networks

S. Khodayifar (), M. A. Raayatpanah () and P. M. Pardalos ()
Additional contact information
S. Khodayifar: Institute for Advanced Studies in Basic Sciences (IASBS)
M. A. Raayatpanah: Kharazmi University
P. M. Pardalos: University of Florida

Annals of Operations Research, 2019, vol. 272, issue 1, No 3, 29-39

Abstract: 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\}$$ { 0 , 1 , … , 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)$$ O ( n 2 m ) .

Keywords: Network flows; Combinatorial optimization; (Dynamic) Minimum flow; (Dynamic) Preflow-pull algorithm (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2450-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:272:y:2019:i:1:d:10.1007_s10479-017-2450-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2450-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().