Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in $O(n^{1.5} \log n)$ Time

Shay Mozes

arxiv: 1012.5870 · v1 · pith:VRJRAB5Cnew · submitted 2010-12-29 · 💻 cs.DM · cs.DS

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in O(n^(1.5) log n) Time

Shay Mozes This is my paper

classification 💻 cs.DM cs.DS

keywords directedflowmaximumnodesplanaralgorithmcapacitiesfinds

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 set of sink nodes, finds a maximum flow from the sources to the sinks.

This paper has not been read by Pith yet.

Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in O(n^(1.5) log n) Time

discussion (0)