Minimum s - t Cut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time

Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge’s cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time $O(n\log ^2 (n))$. For the case when L contains only integers$ \leqq n^{O(1)} $, the algorithm runs in time $O(n\log (n)\log \log (n))$. Our algorithm also constructs a minimum s-t cut of a planar graph (i.e., for the case $L = \{ 1\} $) in time $O(n\log (n))$. Our algorithm can also be used to compute a minimum cut for a general undirected planar network. The fastest previous algorithm for computing a minimum s-t cut of a planar undirected network (Itai and Shiloach [SIAM J. Comput., 8 (1979), pp. 135–150]) has time $O(n^2 \log (n))$; the s-t cut is a byproduct of the maximum flow computed by their algorithm. The best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert and Saxton [report, Dept. Computer Science, Univ. Saskatchewan, 1977]) was $O(n^2 )$.

Duke Scholars

Author John H. Reif Computer Science