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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.