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

Philip N. Klein, Shay Mozes

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 source…