Temporal flows in temporal networks

Akrida, Eleni C ORCID: 0000-0002-1126-1623, Czyzowicz, Jurek, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Kuszner, Lukasz and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2019) Temporal flows in temporal networks. In: 10th International Conference on Algorithms and Complexity -CIAC 2017, 2017-5-24 - 2017-5-26, Athens Greece.

	Text CIAC_paper_12_pages.pdf - Author Accepted Manuscript Download (219kB)
	Atom XML (admin) 2017-05-12T10:15:07Z.atom - Unspecified Access to this file is embargoed until Unspecified. Download (12kB)

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.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Temporal networks, Network flows, Random input, Edge availability
Depositing User:	Symplectic Admin
Date Deposited:	06 Feb 2017 10:29
Last Modified:	19 Jan 2023 07:19
DOI:	10.1016/j.jcss.2019.02.003
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005551