May 4, Wednesday 14:15, Jacobs Building Room 303
Title: Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Lecturer : Shay Mozes
Lecturer homepage : http://www.cs.brown.edu/~shay/
Affiliation : Department of Computer Science, Brown University
We give 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. In general (i.e., non-planar) graphs, multiple sources and sinks can be reduced to the single-source single-sink case by introducing an artificial source and sink and connecting them to all the sources and sinks, respectively. However, this reduction does not preserve planarity. the fastest known algorithm for computing multiple-source multiple-sink max-flow in a planar graph has been to use this reduction in conjunction with a general maximum-flow algorithm such as that of Sleator and Tarjan which leads to a running time of O(n^2 log n). For integer capacities less than U, one could instead use the algorithm of Goldberg and Rao, which leads to a running time of O(n^1.5 log n log U). No planarity-exploiting algorithm was known for the problem. To obtain the result we use pseudoflows, and exploit, among other ideas, a relation between primal circulations and dual shortest paths to maintain a succinct representation of the flow during critical phases of the algorithm. Even though our representation does not explicitly store the flow on nearly any arc in the graph, we can augment it efficiently towards optimality while maintaining feasibility.