Akrida, Eleni C. and Czyzowicz, Jurek and Gąsieniec, Leszek and Kuszner, Łukasz and Spirakis, Paul G. (2019) 'Temporal flows in temporal networks.', Journal of computer and system sciences., 103 . pp. 46-60.
We introduce temporal flows on temporal networks. We show that one can find the maximum amount of flow that can pass from a source vertex s to a sink vertex t up to a given time in Polynomial time. We provide a static Time-Extended network (TEG) of polynomial size to the input, and show that temporal flows can be decomposed into flows, each moving through a single s-t temporal path. We then examine the case of unbounded node buffers. We prove that the maximum temporal flow is equal to the value of the minimum temporal s-t cut. We partially characterise networks with random edge availabilities that tend to eliminate the s-t temporal flow. We also consider mixed temporal networks, where some edges have specified availabilities and some edges have random availabilities; we define the truncated expectation of the maximum temporal flow and show that it is #P-hard to compute it.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives 4.0.
Download PDF (920Kb)
|Publisher Web site:||https://doi.org/10.1016/j.jcss.2019.02.003|
|Publisher statement:||© 2021 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||15 February 2019|
|Date deposited:||26 October 2021|
|Date of first online publication:||25 February 2019|
|Date first made open access:||26 October 2021|
Save or Share this output
|Look up in GoogleScholar|