Multiple-source single-sink maximum flow in directed planar graphs in O(n¹.⁵ n) time

الأصل · EN

We give an O(n¹.⁵ 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.