Continuous and discrete flows over time
Continuous and discrete flows over time
复制标题
随时间变化的连续流和离散流
DOI：
10.1007/s00186-011-0357-2
复制
发表时间：
2011
影响因子：
1.2
通讯作者：
M. Skutella
中科院分区：
文献类型：
--
作者：
Ronald Koch;E. Nasrabadi;M. Skutella
随着时间的推移，网络流形成了一个迷人的研究领域。他们模拟各种应用中出现的网络流问题的时间动态。在这一领域的研究一直在两个不同的，主要是独立的方向进行的时间建模：离散和连续时间模型。在本文中，我们部署测量理论，以引入一个一般模型的网络流量随着时间的推移结合离散和连续的方面到一个单一的模型。这里，每个弧上的流量被建模为真实的线（时间轴）上的Borel测量，其为每个合适的子集分配真实的值，该值被解释为在子集上进入弧的流量。我们专注于最大流问题制定的网络中的能力弧也给出了博雷尔措施和存储可能允许在网络的节点。我们将割的概念推广到这些Borel流的情况，并扩展了著名的MaxFlow-MinCut定理。
Network flows over time form a fascinating area of research. They model the temporal dynamics of network flow problems occurring in a wide variety of applications. Research in this area has been pursued in two different and mainly independent directions with respect to time modeling: discrete and continuous time models. In this paper we deploy measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects into a single model. Here, the flow on each arc is modeled as a Borel measure on the real line (time axis) which assigns to each suitable subset a real value, interpreted as the amount of flow entering the arc over the subset. We focus on the maximum flow problem formulated in a network where capacities on arcs are also given as Borel measures and storage might be allowed at the nodes of the network. We generalize the concept of cuts to the case of these Borel Flows and extend the famous MaxFlow-MinCut Theorem.