AN O(N LOG2 N) ALGORITHM FOR MAXIMUM FLOW IN UNDIRECTED PLANAR NETWORKS

被引：42
|
作者：
HASSIN, R [1 ]
JOHNSON, DB [1 ]
机构：
[1] PENN STATE UNIV,DEPT COMP SCI,UNIVERSITY PK,PA 16802
来源：
SIAM JOURNAL ON COMPUTING | 1985年 / 14卷 / 03期
关键词：
D O I：
10.1137/0214045
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：612 / 624
页数：13
相关论文
共 50 条
  • [1] MINIMUM S-T CUT OF A PLANAR UNDIRECTED NETWORK IN O(N LOG2 (N)) TIME
    REIF, JH
    SIAM JOURNAL ON COMPUTING, 1983, 12 (01) : 71 - 81
  • [2] An O(n log2 n) algorithm for a sink location problem in dynamic tree networks
    Mamada, S
    Uno, T
    Makino, K
    Fujishige, S
    EXPLORING NEW FRONTIERS OF THEORETICAL INFORMATICS, 2004, 155 : 251 - 264
  • [3] A O(n log2 n) Checker and O(n2 log n) Filtering Algorithm for the Energetic Reasoning
    Ouellet, Yanick
    Quimper, Claude-Guy
    INTEGRATION OF CONSTRAINT PROGRAMMING, ARTIFICIAL INTELLIGENCE, AND OPERATIONS RESEARCH, CPAIOR 2018, 2018, 10848 : 477 - 494
  • [4] Shortest Paths in Planar Graphs with Real Lengths in O(n log2 n/log log n) Time
    Mozes, Shay
    Wulff-Nilsen, Christian
    ALGORITHMS-ESA 2010, PT II, 2010, 6347 : 206 - +
  • [5] An O(n log n) Algorithm for Maximum st-Flow in a Directed Planar Graph
    Borradaile, Glencora
    Klein, Philip
    JOURNAL OF THE ACM, 2009, 56 (02)
  • [6] An O(n log n) algorithm for maximum st-flow in a directed planar graph
    Borradaile, Glencora
    Klein, Philip
    PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 524 - 533
  • [7] An O(n log2 n) algorithm for the optimal sink location problem in dynamic tree networks
    Mamada, Satoko
    Uno, Takeaki
    Makino, Kazuhisa
    Fujishige, Satoru
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (16) : 2387 - 2401
  • [8] Simple O(n log2 n) Algorithms for the Planar 2-Center Problem
    Tan, Xuehou
    Jiang, Bo
    COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 481 - 491
  • [9] ORDER N LOG2 N WHT/DHT ALGORITHM
    HSU, CY
    WU, JL
    ELECTRONICS LETTERS, 1988, 24 (06) : 315 - 316
  • [10] O(N2 log2 N) filtered backprojection reconstruction algorithm for tomography
    Basu, S
    Bresler, Y
    IEEE TRANSACTIONS ON IMAGE PROCESSING, 2000, 9 (10) : 1760 - 1773
12345