- Optimal Cuts in Surface Imb...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in April 2014
Optimal Cuts in Surface Imbedded Graphs
Speaker:
Kyle Fox
, ICERM
Date: Wednesday, April 02, 2014
Time: 4:30 PM to 5:30 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-G575
Event Type:
Room Description:
Host: Ilya Razenshteyn
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Relevant URL: http://toc.csail.mit.edu/node/421
Speaker URL: None
Speaker Photo:
None
Reminders to:
theory-seminars@csail.mit.edu, seminars@csail.mit.edu
Reminder Subject:
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.
Research Areas:
Impact Areas:
Created by Rebecca Yadegar 
at Tuesday, March 25, 2014 at 4:35 PM.