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

« February 2018 »
Upcoming Events
Algebra Seminar
Tue, Feb 20, 2018
Complex and Arithmetic Dynamics of Monomial Maps Jan-Li Lin, Saint Louis, MO
AWM Meeting
Tue, Feb 20, 2018
Student Chapter of the Association of Women in Mathematics Organizational Meeting
Wed, Apr 18, 2018
Quantitative Topology? by Shmuel Weinberger, U Chicago
Previous events…
Upcoming events…