Minimum s-t cut of a planar undirected network in o(n log²(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 log2(n)) time on a (uniform cost criteria) RAM. For the case L contains only integers ≤n0(1), the algorithm runs in time O(n log(n)loglog(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)). The fastest previous algorithm for computing a minimum s-t cut of a planar undirected network [Gomory and Hu, 1961] and [Itai and Shiloach, 1979] has time O(n2 log(n)) and the best previous time bound for minimum s-t cut of a planar graph (Cheston, Probert, and Saxton, 1977] was O(n2).

Duke Scholars

Author John H. Reif Computer Science