Personal tools

Divide & Conquer Algorithms for Network Flow Problems in Planar Graphs

— filed under:

Dr. Glencora Borradaile, Oregon State University

  • Computer Science Seminar
When Wed, Jun 26, 2013
from 12:00 PM to 12:50 PM
Where Ritter Hall 128
Add event to calendar vCal

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).

« September 2017 »