Stable Flows over Time
Stable Flows over Time
复制标题
随着时间的推移稳定的流量
作者：
Ágnes Cseh;J. Matuschke;M. Skutella
本文将稳定性的概念推广到随时间变化的网络流中。作为我们证明中的一个有用的工具，我们提出了Gale-Shapley算法的一个精巧的预流推变体，它直接在给定的网络上操作，并且在伪多项式时间内计算稳定的流，无论是在静态流还是随时间流动的情况下都是如此。我们证明了具有无限时间范围的网络上稳定流随时间的周期性。最后，我们讨论了顶点存储的影响，不同的结果取决于对应的保留边的优先级。
In this paper, the notion of stability is extended to network flows over time. As a useful device in our proofs, we present an elegant preflow-push variant of the Gale-Shapley algorithm that operates directly on the given network and computes stable flows in pseudo-polynomial time, both in the static flow and the flow over time case. We show periodical properties of stable flows over time on networks with an infinite time horizon. Finally, we discuss the influence of storage at vertices, with different results depending on the priority of the corresponding holdover edges.