Temporal flows in temporal networks

Eleni C. Akrida , Jurek Czyżowicz , 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 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 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.
Author Eleni C. Akrida
Eleni C. Akrida,,
-
, Jurek Czyżowicz
Jurek Czyżowicz,,
-
, Leszek Gąsieniec
Leszek Gąsieniec,,
-
, Łukasz Kuszner (FMPI / II)
Łukasz Kuszner ,,
- Institute of Informatics
, Paul G. Spirakis
Paul G. Spirakis,,
-
Journal seriesJournal of Computer and System Sciences, ISSN 0022-0000, (A 30 pkt)
Issue year2019
Vol103
Pages46-60
Publication size in sheets0.7
Keywords in Englishtemporal networks, network flows, random input, edge availability
ASJC Classification2604 Applied Mathematics; 1703 Computational Theory and Mathematics; 1705 Computer Networks and Communications; 2614 Theoretical Computer Science
DOIDOI:10.1016/j.jcss.2019.02.003
URL https://doi.org/10.1016/j.jcss.2019.02.003
Languageen angielski
Score (nominal)30
ScoreMinisterial score = 30.0, 24-07-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2016 = 1.768; WoS Impact Factor: 2017 = 1.497 (2) - 2017=1.914 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back