Minimum Cut of Directed Planar Graphs in O(nloglogn) Time

Shay Mozes, Cyril Nikolaev, Yahav Nussbaum +1

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 fas…