A topological max-flow-min-cut theorem
A topological max-flow-min-cut theorem
复制标题
拓扑最大流最小割定理
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Sanjeevi Krishnan
中科院分区：
文献类型：
--
作者：
R. Ghrist;Sanjeevi Krishnan
本文综述了容量约束下有向网络的最大流最小割定理的一个新的代数拓扑形式。新功能包括将容量约束编码为网络上的半模块层，以及将流和截值实现为取层中值的有向同调。我们综述了这个定理，并给出了它在（1）多商品流，（2）多源/多目标流和（3）布尔格值流中的应用。
This note surveys a novel algebraic-topological version of the max-flow-min-cut (MFMC) theorem for directed networks with capacity constraints. Novel features include the encoding of capacity constraints as a sheaf of semimodules over the network and a realization of flow and cut values as a directed homology taking values in the sheaf. We survey the theorem and give applications to (1) multicommodity flows, (2) multi-source/multi-target flows, and (3) boolean-lattice-valued flows.