Minimum S-T Cut of a Planar Undirected Network in O(n log2(n)) Time

摘要

We have presented an algorithm for computing a minimum s-t cut of a planar undirected network. Our algorithm runs in an order of magnitude less time than previous algorithms for this problem. An additional attractive feature of this algorithm is its simplicity, as compared to certain other algorithms for computing minimum s-t cuts for sparse networks.