Dr Eleni Akrida eleni.akrida@durham.ac.uk
Associate Professor
Temporal Flows in Temporal Networks
Akrida, Eleni C.; Czyzowicz, Jurek; Gąsieniec, Leszek; Kuszner, Łukasz; Spirakis, Paul G.
Authors
Jurek Czyzowicz
Leszek Gąsieniec
Łukasz Kuszner
Paul G. Spirakis
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.
Citation
Akrida, E. C., Czyzowicz, J., Gąsieniec, L., Kuszner, Ł., & Spirakis, P. G. (2017). Temporal Flows in Temporal Networks. In Algorithms and Complexity (43-54). https://doi.org/10.1007/978-3-319-57586-5_5
Conference Name | 10th International Conference in Algorithms and Complexity, CIAC 2017 |
---|---|
Conference Location | Athens, Greece |
Online Publication Date | Apr 14, 2017 |
Publication Date | 2017 |
Deposit Date | Oct 25, 2021 |
Publicly Available Date | Oct 26, 2021 |
Volume | 10236 |
Pages | 43-54 |
Series Title | Lecture Notes in Computer Science |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Algorithms and Complexity |
ISBN | 9783319575858 |
DOI | https://doi.org/10.1007/978-3-319-57586-5_5 |
Files
Accepted Conference Proceeding
(219 Kb)
PDF
Copyright Statement
The final authenticated version is available online at https://doi.org/10.1007/978-3-319-57586-5_5
You might also like
Narrowing and Stretching: Addressing the Challenge of Multi-track Programming
(2022)
Conference Proceeding
Connected Subgraph Defense Games
(2021)
Journal Article
The temporal explorer who returns to the base
(2021)
Journal Article
How fast can we reach a target vertex in stochastic temporal graphs?
(2020)
Journal Article
Connected Subgraph Defense Games
(2019)
Book Chapter
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search