Given is a connected positively weighted undirected planar graph G embedded in the plane, a source vertex s, and a set of sink vertices T. An (s,T)-cut in G corresponds to a cycle or a collection of edge-disjoint cycles in the planar dual graph G~* that define a planar region containing s but not T. A cut with a connectivity prior does not separate the vertices in T from each other: we focus on the most natural prior where the cut corresponds to a (simple, i.e., no repeated vertices) cycle in G~*. We present an algorithm that finds a minimum simple (s, T)-cut in O(n~4) time for n vertices. To the best of our knowledge, this is the first polynomial-time algorithm for minimum cuts with connectivity priors. Such cuts have applications in computer vision and medical imaging.
展开▼
