Temporal flows in temporal networks
Temporal flows in temporal networks
复制标题
DOI：
10.1016/j.jcss.2019.02.003
复制
发表时间：
2019-08-01
影响因子：
1.1
通讯作者：
Spirakis, Paul G.
中科院分区：
文献类型：
--
作者：
Akrida, Eleni C.;Czyzowicz, Jurek;Spirakis, Paul G.
我们介绍了时间网络上的时间流。我们可以找到的最大量的流量，可以通过从源顶点s到汇顶点t到给定的时间在多项式时间。我们提供了一个静态的时间扩展网络（TEG）的多项式大小的输入，并表明，时间流可以分解成流，每个移动通过一个单一的s-t的时间路径。我们证明了最大时间流等于最小时间s-t截的值。我们用随机边可用性部分地验证了网络，这些随机边可用性倾向于消除s-t时间流。我们还考虑了混合时间网络，其中一些边具有指定的可用性，一些边具有随机可用性;我们定义了最大时间流的截断期望，并证明了计算它是#P-hard的。All rights reserved.
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. (C) 2019 Elsevier Inc. All rights reserved.