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

被引：34

作者：

Borradaile, Glencora ^{[1
]}

Klein, Philip N. ^{[2
]}

Mozes, Shay ^{[3
]}

Nussbaum, Yahav ^{[4
]}

Wulff-Nilsen, Christian ^{[5
]}

机构：

[1] Oregon State Univ, Sch Elect Engn & Comp Sci, Corvallis, OR 97331 USA

[2] Brown Univ, Dept Comp Sci, Providence, RI 02912 USA

[3] Efi Arazi Sch Comp Sci, Interdisciplinary Ctr, Herzliyya, Israel

[4] Tel Aviv Univ, Blavatnik Sch Comp Sci, Tel Aviv 69978, Israel

[5] Univ Copenhagen, Dept Comp Sci, DK-1017 Copenhagen, Denmark

来源：

SIAM JOURNAL ON COMPUTING | 2017年 / 46卷 / 04期

基金：

美国国家科学基金会;

关键词：

planar graphs; maximum flow; SHORTEST PATHS; ENERGY MINIMIZATION; ALGORITHMS; CUTS;

D O I：

10.1137/15M1042929

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：1280 / 1303

页数：24

共 45 条

[1] A survey of very large-scale neighborhood search techniques [J].

Ahuja, RK ;

Ergun, Ö ;

Orlin, JB ;

Punnen, AP .

DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :75-102

[2]

[Anonymous], P 45 S THEOR COMP ST, DOI DOI 10.1145/2488608.2488705

[3]

[Anonymous], 2014, THESIS

[4]

BORRADAILE G., 2016, 32 INT S COMP GEOM L, V51, P22

[5] An O(n log n) Algorithm for Maximum st-Flow in a Directed Planar Graph [J].

Borradaile, Glencora ;

Klein, Philip .

JOURNAL OF THE ACM, 2009, 56 (02)

[6] Fast approximate energy minimization via graph cuts [J].

Boykov, Y ;

Veksler, O ;

Zabih, R .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2001, 23 (11) :1222-1239

[7] An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision [J].

Boykov, Y ;

Kolmogorov, V .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004, 26 (09) :1124-1137

[8] MULTIPLE-SOURCE SHORTEST PATHS IN EMBEDDED GRAPHS [J].

Cabello, Sergio ;

Chambers, Erin W. ;

Erickson, Jeff .

SIAM JOURNAL ON COMPUTING, 2013, 42 (04) :1542-1571

[9]

Chambers E, 2010, LECT NOTES COMPUT SC, V6506, P241, DOI 10.1007/978-3-642-17517-6_23

[10] Accelerated bend minimization [J].

Cornelsen, Sabine ;

Karrenbauer, Andreas .

Journal of Graph Algorithms and Applications, 2012, 16 (03) :635-650

← 1 2 3 4 5 →