On Stable Matchings and Flows
On Stable Matchings and Flows
复制标题
论稳定匹配和流量
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
T. Fleiner
中科院分区：
文献类型：
--
作者：
T. Fleiner
我们描述了一个流模型相关的普通网络流的稳定匹配相关的最大匹配在二分图中相同的方式。证明了稳定流的存在性，并将稳定婚姻的格结构推广到稳定流。我们的主要工具是一个简单的减少稳定流问题的稳定分配。为了完整性，我们证明了我们需要的结果稳定的分配作为一个应用塔斯基的不动点定理。
We describe a flow model related to ordinary network flows the same way as stable matchings are related to maximum matchings in bipartite graphs. We prove that there always exists a stable flow and generalize the lattice structure of stable marriages to stable flows. Our main tool is a straightforward reduction of the stable flow problem to stable allocations. For the sake of completeness, we prove the results we need on stable allocations as an application of Tarski’s fixed point theorem.