Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Speaker: Shay Mozes, CSAIL, MIT
Date: Tuesday, November 13 2012
Time: 4:15PM to 5:15PM
Location: 32-124 Stata Center
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, email@example.comRelevant URL:
I will present an an O(n log^3 n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.