Minimum Cut of Directed Planar Graphs in O(n log log n) Time
Minimum Cut of Directed Planar Graphs in O(n log log n) Time
复制标题
O(n log log n) 时间内有向平面图的最小割
DOI：
10.1137/1.9781611975031.32
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Oren Weimann
中科院分区：
文献类型：
--
作者：
S. Mozes;Kirill Nikolaev;Yahav Nussbaum;Oren Weimann
给出了一个计算赋权有向平面图的最小割(或等价的最短圈)的$O(n\log\logn)$time算法。这改进了以前最快的$O(n\log^3 n)$解决方案。有趣的是，在无向平面图中，最小割和最小$st$-Cut都有$O(n\log\logn)$解，而在有向平面图中，我们的结果使最小割比最小$st$-Cut快，后者目前需要$O(n\logn)$。
We give an $O(n \log \log n)$ time algorithm for computing the minimum cut (or equivalently, the shortest cycle) of a weighted directed planar graph. This improves the previous fastest $O(n\log^3 n)$ solution. Interestingly, while in undirected planar graphs both min-cut and min $st$-cut have $O(n \log \log n)$ solutions, in directed planar graphs our result makes min-cut faster than min $st$-cut, which currently requires $O(n \log n)$.