CS 269S, Winter 2012: Theory Seminar
Bren Hall, Room 1423
3 Feb 2012:

Global Minimum Cuts in Surface Embedded Graphs

Presenter: Lowell Trott

Jeff Erickson, Kyle Fo, Amir Nayyeri

The authors give a deterministic algorithm to find the minimum cut in a surface-embedded graph in near-linear time. Given an undirected graph embedded on an orientable surface of genus g, our algorithm computes the minimum cut in g^{O(g)}*nloglogn time, matching the running time of the fastest algorithm known for planar graphs, due to .a .cki and Sankowski, for any constant g.