Minimum Cut of Directed Planar Graphs in O ( n log log n ) Time
Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, Oren Weimann · Society for Industrial and Applied Mathematics eBooks · 2018
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 log3 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).