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


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(n2 log n) time. We present an O(n log3 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" [...]


  The system of instant Payday Loans Virginia allows any adult U.S. citizen. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis Online is the one that definitely differs from all other products.