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 条
  • [11] MINIMUM CUTS AND SPARSIFICATION IN HYPERGRAPHS
    Chekuri, Chandra
    Xu, Chao
    SIAM JOURNAL ON COMPUTING, 2018, 47 (06) : 2118 - 2156
  • [12] RANDOMIZED APPROXIMATION SCHEMES FOR CUTS AND FLOWS IN CAPACITATED GRAPHS
    Benczur, Andras A.
    Karger, David R.
    SIAM JOURNAL ON COMPUTING, 2015, 44 (02) : 290 - 319
  • [13] Homology Flows, Cohomology Cuts
    Chambers, Erin W.
    Erickson, Jeff
    Nayyeri, Amir
    STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2009, : 273 - 281
  • [14] HOMOLOGY FLOWS, COHOMOLOGY CUTS
    Chambers, Erin W.
    Erickson, Jeff
    Nayyeri, Amir
    SIAM JOURNAL ON COMPUTING, 2012, 41 (06) : 1605 - 1634
  • [15] A New Approach to Computing Maximum Flows using Electrical Flows
    Lee, Yin Tat
    Rao, Satish
    Srivastava, Nikhil
    STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2013, : 755 - 764
  • [16] Minimum Cuts and Shortest Homologous Cycles
    Chambers, Erin W.
    Erickson, Jeff
    Nayyeri, Amir
    PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, : 377 - 385
  • [17] Achieving Minimum-Routing-Cost Maximum-Flows in Infrastructure Wireless Mesh Networks
    Szymanski, T. H.
    2012 IEEE WIRELESS COMMUNICATIONS AND NETWORKING CONFERENCE (WCNC), 2012,
  • [18] Flows, cuts and integral routing in graphs - an approximation algorithmist's perspective
    Chuzhoy, Julia
    PROCEEDINGS OF THE INTERNATIONAL CONGRESS OF MATHEMATICIANS (ICM 2014), VOL IV, 2014, : 585 - 607
  • [19] COUNTING THE NUMBER OF MINIMUM CUTS IN UNDIRECTED MULTIGRAPHS
    NAGAMOCHI, H
    SUN, Z
    IBARAKI, T
    IEEE TRANSACTIONS ON RELIABILITY, 1991, 40 (05) : 610 - 614
  • [20] EXTRACTING MAXIMAL INFORMATION ABOUT SETS OF MINIMUM CUTS
    GUSFIELD, D
    NAOR, D
    ALGORITHMICA, 1993, 10 (01) : 64 - 89