Maximum flows and minimum cuts in the plane

被引:12
作者
Strang, Gilbert [1 ]
机构
[1] MIT, Cambridge, MA 02139 USA
关键词
Maximum flow; Minimum cut; Capacity constraint; Cheeger; ENERGY MINIMIZATION; MAX-FLOW;
D O I
10.1007/s10898-009-9471-6
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
A continuous maximum flow problem finds the largest t such that div v = t F(x, y) is possible with a capacity constraint ||(v (1), v (2))|| a parts per thousand currency sign c(x, y). The dual problem finds a minimum cut a, S which is filled to capacity by the flow through it. This model problem has found increasing application in medical imaging, and the theory continues to develop (along with new algorithms). Remaining difficulties include explicit streamlines for the maximum flow, and constraints that are analogous to a directed graph.
引用
收藏
页码:527 / 535
页数:9
相关论文
共 50 条
  • [41] Counting and sampling minimum (s, t)-cuts in weighted planar graphs in polynomial time
    Bezakova, Ivona
    Friedlander, Adam J.
    THEORETICAL COMPUTER SCIENCE, 2012, 417 : 2 - 11
  • [42] Minimum+1 (s, t)-cuts and Dual-edge Sensitivity Oracle
    Baswana, Surender
    Bhanja, Koustav
    Pandey, Abhyuday
    ACM TRANSACTIONS ON ALGORITHMS, 2023, 19 (04)
  • [43] Minimum flows in directed s-t planar networks
    Georgescu, Oana
    Ciurea, Eleonor
    BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE, 2010, 53 (04): : 305 - 313
  • [44] Holiest Minimum-Cost Paths and Flows in Surface Graphs
    Erickson, Jeff
    Fox, Kyle
    Lkhamsuren, Luvsandondov
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 1319 - 1332
  • [45] Image Segmentation Using Graph Cuts Based on Maximum-Flow Neural Network
    Sato, Masatoshi
    Toda, Hideharu
    Aomori, Hisashi
    Otake, Tsuyoshi
    Tanaka, Mamoru
    NEURAL INFORMATION PROCESSING, ICONIP 2016, PT I, 2016, 9947 : 403 - 412
  • [46] The maximum flows in bipartite dynamic networks. The static approach
    Schiopu, Camelia
    ANNALS OF THE UNIVERSITY OF CRAIOVA-MATHEMATICS AND COMPUTER SCIENCE SERIES, 2016, 43 (02): : 200 - 209
  • [47] Maximum Flows in Planar Dynamic Networks. The Static Approach
    Schiopu, Camelia
    Ciurea, Eleonor
    ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 2020, 23 (0T): : T18 - T27
  • [48] Maximizing Flows with Message-Passing: Computing Spatially Continuous Min-Cuts
    Bae, Egil
    Tai, Xue-Cheng
    Yuan, Jing
    ENERGY MINIMIZATION METHODS IN COMPUTER VISION AND PATTERN RECOGNITION, EMMCVPR 2015, 2015, 8932 : 15 - 28
  • [49] APPROXIMATING THE MINIMUM-COST MAXIMUM FLOW IS P-COMPLETE
    STEIN, C
    WEIN, J
    INFORMATION PROCESSING LETTERS, 1992, 42 (06) : 315 - 319
  • [50] MINIMUM CUTS AND SHORTEST CYCLES IN DIRECTED PLANAR. GRAPHS VIA NONCROSSING SHORTEST PATHS
    Liang, Hung-Chun
    Lu, Hsueh-I
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (01) : 454 - 476