MULTIPLE-SOURCE MULTIPLE-SINK MAXIMUM FLOW IN DIRECTED PLANAR GRAPHS IN NEAR-LINEAR TIME

作者：Borradaile Glencora^*; Klein Philip N; Mozes Shay; Nus**aum Yahav; Wulff Nilsen Christian

来源：SIAM Journal on Computing, 2017, 46(4): 1280-1303.

DOI：10.1137/15M1042929

• planar graphs
• maximum flow

We give an O(n log(3) 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.

• 出版日期2017