Temporal flows in temporal networks

Akrida, Eleni C.; Czyzowicz, Jurek; Gąsieniec, Leszek; Kuszner, Łukasz; Spirakis, Paul G.

Abstract

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.

Citation

Akrida, E. C., Czyzowicz, J., Gąsieniec, L., Kuszner, Ł., & Spirakis, P. G. (2019). Temporal flows in temporal networks. Journal of Computer and System Sciences, 103, 46-60. https://doi.org/10.1016/j.jcss.2019.02.003

• Journal Article Type: Article
• Acceptance Date: Feb 15, 2019
• Online Publication Date: Feb 25, 2019
• Publication Date: 2019-08
• Deposit Date: Jun 20, 2020
• Publicly Available Date: Oct 26, 2021
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Electronic ISSN: 1090-2724
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 103
• Pages: 46-60
• DOI: https://doi.org/10.1016/j.jcss.2019.02.003
• Public URL: https://durham-repository.worktribe.com/output/1268041