论文标题
在稳定的流量和预回事上
On stable flows and preflows
论文作者
论文摘要
在2010年代，Fleiner在有向网络中引入了稳定流的概念，并表明这种流程始终存在，可以通过将Baiou和Balinski引起的稳定分配问题减少来找到。最近，CSEH和MATUSCHKE设计了一种直接强烈的多项式算法。在本文中，我们提供了一种替代算法，以在具有多个来源和水槽的网络中找到稳定的流量。它基于预流的想法（1970年代以更快的算法出现，用于经典的最大流问题），并以$ o（nm）$时间运行，该网络具有$ n $ dertices和$ m $ edges的网络。结果进一步推广到较大类别的对象，即在非末端顶点中具有有限过量的所谓稳定准流量。 （该论文用俄语编写。）
In 2010s Fleiner introduced a notion of stable flows in directed networks and showed that such a flow always exists and can be found by use of a reduction to the stable allocation problem due to Baiou and Balinski. Recently Cseh and Matuschke devised a direct strongly polynomial algorithm. In this paper we give an alternative algorithm to find a stable flow in a network with several sources and sinks. It is based on an idea of preflows (appeared in 1970s in a faster algorithm for the classical max-flow problem), and runs in $O(nm)$ time for a network with $n$ vertices and $m$ edges. The results are further generalized to a larger class of objects, so-called stable quasi-flows with bounded excesses in non-terminal vertices. (The paper is written in Russian.)
