Abstract:

An algorithm which for any planar directed network with n nodes finds its minimum cut in time $O(n log^2(n)/ log (log (n)))$ is presented. For the case of s-t -network this time is reduced by the factor of $log (n)$, i. e. to $O(n log (n)/log (log (n)))$.