Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
复制标题
O(直径·n log n)时间内有向平面图中的多源单汇最大流量
DOI：
10.1007/978-3-642-22300-6_48
复制
发表时间：
2011
影响因子：
2.7
通讯作者：
S. Mozes
中科院分区：
文献类型：
--
作者：
P. Klein;S. Mozes
我们开发了一种新技术，用于计算具有多个来源的有向平面图和一个单一的水槽，这与先前已知的流量问题显着偏离了流量问题。
We develop a new technique for computing maximum flow in directed planar graphs with multiple sources and a single sink that significantly deviates from previously known techniques for flow problems. This gives rise to an O(diameter ċ nlogn) algorithm for the problem.