hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We give an algorithm to find a mincut in an $n$-vertex, $m$-edge weighted
directed graph using $\tilde O(\sqrt{n})$ calls to any maxflow subroutine.
Using state of the art maxflow algorithms, this yields a directed mincut
algorithm that runs in $\tilde O(m\sqrt{n} + n^2)$ time. This improves on the
30 year old bound of $\tilde O(mn)$ obtained by Hao and Orlin for this problem.
