Min st-Cut of a Planar Graph in O(n loglog n) Time
Christian Wulff‐Nilsen · arXiv (Cornell University) · 2010
Given a planar undirected n-vertex graph G with non-negative edge weights, we show how to compute, for given vertices s and t in G, a min st-cut in G in O(n loglog n) time and O(n) space. The previous best time bound was O(n log n).