Temporal flows in temporal networks

摘要

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.