






















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)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。