Eastern Great Lakes Theory Workshop Talk

Contiguous minimum single-source-multi-sink cuts in weighted planar graphs

Ivona Bezáková, Rochester Institute of Technology

Sunday, September 11, 10:30am-11:30am

ABSTRACT

We will present a fast algorithm for uniform sampling of contiguous minimum cuts separating a source vertex from a set of sink vertices in a weighted planar graph with n vertices. The algorithm takes O(n) time per sample, after an initial O(n^3) preprocessing time during which the algorithm computes the number of all such contiguous minimum cuts. Contiguous cuts (that is, cuts where the cut set can be separated from the remaining vertices by a simply connected planar region whose boundary intersects only the cut edges) have applications in computer vision and medical imaging.

The counting algorithm has two phases. First, we reduce the problem to the problem of counting certain non-crossing tours in the dual of a planar directed acyclic graph. Next, we show how to decompose the dual graph into several edge-disjoint (but not vertex-disjoint) directed acyclic graphs so that a tour is non-crossing if and only if it is a concatenation of some easy-to-find paths in these graphs. An interesting aspect of this decomposition is that the paths can be found/sampled independently and the resulting tour is guaranteed to be non-crossing. This allows us to count all needed non-crossing tours using dynamic programming.

Based on joint work with Zach Langley.

Speaker Bio

Ivona Bezakova is an assistant professor in the Department of Computer Science at Rochester Institute of Technology. She received her undergraduate degree from the Comenius University (Slovakia) in 2000, and her doctorate degree from the University of Chicago in 2006. Her main research interests lie in theoretical computer science, with emphasis on sampling and (approximate) counting of discrete structures.

< Schedule < EaGL-IV homepage