Skip to main content

Research Repository

Advanced Search

Temporal flows in temporal networks

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

Temporal flows in temporal networks Thumbnail


Authors

Jurek Czyzowicz

Leszek Gąsieniec

Łukasz Kuszner

Paul G. Spirakis



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
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 103
Pages 46-60
DOI https://doi.org/10.1016/j.jcss.2019.02.003

Files





You might also like



Downloadable Citations