Counting and sampling minimum (s, t)-cuts in weighted planar graphs in polynomial time
We give an O(nd + n log n) algorithm computing the number of minimum (s, t)-cuts in weighted planar graphs, where n is the number of vertices and d is the length of the shortest s-t path in the corresponding unweighted graph. Previously, Ball and Provan gave a polynomial-time algorithm for unweighted planar graphs with both s and t lying on the outer face. Our results hold for all locations of s and t and weighted graphs, and have direct applications in computer vision. (C) 2011 Elsevier B.V. All rights reserved.
counting and sampling minimum (s, t)-cuts weighted planar graphs maximum flow maximal antichains in partially ordered sets