**Friday, 15:45 - 16:10 h, Room: H 3008**

**Yahav Nussbaum**

Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time

**Coauthors: Glencora Borradaile, Philip N. Klein, Shay Mozes, Christian Wulff-Nilsen**

**Abstract:**

We consider the problem of finding a maximum flow from a set of source nodes to a set of sink nodes in an *n*-node directed planar graph with arc capacities. The multiple-source multiple-sink maximum flow problem can be solved using a standard single-source single-sink maximum flow algorithm, as there is a simple reduction which connects a single super-source to the set of sources and the set of sinks to a single super-sink. However, this reduction does not preserve the planarity of the graph, and we have to use a maximum flow algorithm for general (non-planar) graphs in conjunction with the reduction, which requires *O(n*^{2} *log* n) time. We present an *O(n **log*^{3} n) algorithm for the problem. This is the first algorithm for the problem that exploits the planarity of the graph to get a faster time bound. Our algorithm combines wide range of techniques, including pseudoflows, flow partitioning scheme, the duality between flow circulation and shortest paths in planar graphs, succinct representation of a flow in a planar graph, and other planarity-exploiting algorithms.

%

This work was presented at FOCS 2011.

Talk 2 of the invited session Fri.3.H 3008

**"Faster algorithms for network flow problems"** [...]

Cluster 2

**"Combinatorial optimization"** [...]