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
    Ahuja, RK
    Ergun, Ö
    Orlin, JB
    Punnen, AP
    [J]. 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
    Borradaile, Glencora
    Klein, Philip
    [J]. JOURNAL OF THE ACM, 2009, 56 (02)
  • [6] Fast approximate energy minimization via graph cuts
    Boykov, Y
    Veksler, O
    Zabih, R
    [J]. 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
    Boykov, Y
    Kolmogorov, V
    [J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004, 26 (09) : 1124 - 1137
  • [8] MULTIPLE-SOURCE SHORTEST PATHS IN EMBEDDED GRAPHS
    Cabello, Sergio
    Chambers, Erin W.
    Erickson, Jeff
    [J]. 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] Cornelsen Sabine, 2012, Journal of Graph Algorithms and Applications, V16, P635, DOI 10.7155/jgaa.00265
12345