Kybernetika 28 no. 1, 37-49, 1992

Minimum cut in directed planar networks

Ladislav Janiga and Václav Koubek

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)))$.

Classification:

90C60, 90B10, 05C85, 90C35