Optimal Cuts in Surface Imbedded Graphs
Date: Wednesday, April 02, 2014
Time: 4:30 PM to 5:30 PM Note: all times are in the Eastern Time Zone
Host: Ilya Razenshteyn
Contact: Rebecca Yadegar, email@example.com
Relevant URL: http://toc.csail.mit.edu/node/421
Speaker URL: None
TALK: Algorithms & Complexity Seminar: Kyle Fox
In this talk, I will describe some recent algorithmic results related to computing optimal flows and cuts in surface embedded graphs. These results are motivated by a desire to bring our understanding of efficient planar flow and cut algorithms to more general classes of graphs.
I will begin by sketching an algorithm to compute a global minimum cut in an embedded genus g undirected graph. The algorithm runs in time g^O(g) n log log n. For constant g, this running time is a polylogarithmic improvement over the best known running time for sparse graphs due to Karger. Unlike Kargers algorithm, the one I will describe is deterministic
Second, I will describe an algorithm for counting minimum s,t-cuts in an embedded genus g directed graph. This problem has applications in image segmentation, and despite the problem being #P-complete in general, the algorithm I will describe runs in 2^O(g) n^2 time. The algorithm can also be used to aid in sampling minimum s,t-cuts uniformly at random.
When the genus is constant, both algorithms I will describe match the running time of the best known planar graph algorithms for their respective problems. I will conclude the talk by discussing some future work and open problems in this area of research.
This talk is based on work done with Erin W. Chambers, Jeff Erickson, and Amir Nayyeri.
Created by Rebecca Yadegar at Tuesday, March 25, 2014 at 4:35 PM.