Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Temporal Flows in Temporal Networks

Akrida, Eleni C. and Czyzowicz, Jurek and Gąsieniec, Leszek and Kuszner, Łukasz and Spirakis, Paul G. (2017) 'Temporal Flows in Temporal Networks.', in Algorithms and Complexity. , pp. 43-54. Lecture Notes in Computer Science., 10236

Abstract

We introduce temporal flows on temporal networks [17, 19], i.e., networks the links of which exist only at certain moments of time. Such networks are ephemeral in the sense that no link exists after some time. Our flow model is new and differs from the “flows over time” model, also called “dynamic flows” in the literature. We show that the problem of finding the maximum amount of flow that can pass from a source vertex s to a sink vertex t up to a given time is solvable in Polynomial time, even when node buffers are bounded. We then examine mainly the case of unbounded node buffers. We provide a simplified static Time-Extended network ( STEG ), which is of polynomial size to the input and whose static flow rates are equivalent to the respective temporal flow of the temporal network; using STEG , we prove that the maximum temporal flow is equal to the minimum temporal s-t cut. We further show that temporal flows can always be decomposed into flows, each of which moves only through a journey, i.e., a directed path whose successive edges have strictly increasing moments of existence. We partially characterise networks with random edge availabilities that tend to eliminate the s→t temporal flow. We then consider mixed temporal networks, which have some edges with specified availabilities and some edges with random availabilities; we show that it is #P-hard to compute the tails and expectations of the maximum temporal flow (which is now a random variable) in a mixed temporal network.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(215Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-319-57586-5_5
Publisher statement:The final authenticated version is available online at https://doi.org/10.1007/978-3-319-57586-5_5
Date accepted:No date available
Date deposited:26 October 2021
Date of first online publication:14 April 2017
Date first made open access:26 October 2021

Save or Share this output

Export:
Export
Look up in GoogleScholar