Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time

Philip N. Klein; Shay Mozes

arxiv: 1008.5332 · v2 · pith:JQ4JGYVCnew · submitted 2010-08-31 · 💻 cs.DS · cs.DM

Multiple-source single-sink maximum flow in directed planar graphs in O(n^(1.5) log n) time

Philip N. Klein , Shay Mozes This is my paper

classification 💻 cs.DS cs.DM

keywords algorithmdirectedflowmaximumplanarsinkcapacitiesfinds

0 comments

read the original abstract

We give an $O(n^{1.5} \log n)$ algorithm that, given a directed planar graph with arc capacities, a set of source nodes and a single sink node, finds a maximum flow from the sources to the sink . This is the first subquadratic-time strongly polynomial algorithm for the problem.

This paper has not been read by Pith yet.

Multiple-source single-sink maximum flow in directed planar graphs in O(n^(1.5) log n) time

discussion (0)