Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
Borradaile, Glencora · Klein, Philip N. · Mozes, Shay · Nussbaum, Yahav · Wulff-Nilsen, Christian
Original · EN
We give an O(n log³ n) algorithm that, given an n-node 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. Previously, the fastest algorithms known for this problem were those for general graphs.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.