Event Type:

Number Theory Seminar

Date/Time:

Friday, January 17, 2014 - 04:00

Location:

Wngr 285

Guest Speaker:

Institution:

School of EECS, Oregon State

Abstract:

I will discuss recent O(n polylog n)-time algorithms for the all-pairs min cut [FOCS'10] and multi-source, multi-sink max flow [FOCS'11] problems. The fastest known algorithms prior to these results were quadratic. Both algorithms use planar separators as a basis for divide and conquer. The simpler problem that is solved

recursively is a simple min-cut problem and single-source, single sink max flow problem, respectively. Both these simpler problems exhibit technical challenges. In the former problem, a min cut must be computed in the entire graph while spending time proportional to a small piece of the graph resulting from the divide step. In the latter problem, the flow at the vertices of the separator need not be balanced and must be rerouted for feasibility. We will review many key results of planar graphs (planar separators and planar duality) and of network flows (cut-equivalent trees and pseudo-flows).