CSAIL Event Calendar

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

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.

The main new tool is a procedure for computing a sequence of exact st-max-flow computations in an n-node graph that takes roughly O(\sqrt n) time per computation. The procedure is based on a beautiful relation between circulations in a planar graph and shortest paths in its planar dual.

Based on joint work with Gelncora Borradaile, Philip Klein, Yahav Nussbaum and Christian Wulff-Nilsen.

See other events that are part of Theory Colloquium 2012/2013

See other events happening in November 2012