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 条
  • [1] Maximum Flows and Minimum Cuts in the Plane
    Strang, Gilbert
    ADVANCES IN APPLIED MATHEMATICS AND GLOBAL OPTIMIZATION, 2009, 17 : 1 - 11
  • [2] Maximum flows and minimum cuts in the plane
    Gilbert Strang
    Journal of Global Optimization, 2010, 47 : 527 - 535
  • [3] Inverse problem of minimum cuts
    Jianzhong Zhang
    Mao -Cheng Cai
    Mathematical Methods of Operations Research, 1998, 47 : 51 - 58
  • [4] Inverse problem of minimum cuts
    Zhang, JZ
    Cai, MC
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 1998, 47 (01) : 51 - 58
  • [5] A fast algorithm for cactus representations of minimum cuts
    Hiroshi Nagamochi
    Yoshitaka Nakao
    Toshihide Ibaraki
    Japan Journal of Industrial and Applied Mathematics, 2000, 17
  • [6] A fast algorithm for cactus representations of minimum cuts
    Nagamochi, H
    Nakao, Y
    Ibaraki, T
    JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS, 2000, 17 (02) : 245 - 264
  • [7] Rapidly solving an online sequence of maximum flow problems with extensions to computing robust minimum cuts
    Altner, Doug
    Ergun, Oezlem
    INTEGRATION OF AI AND OR TECHNIQUES IN CONSTRAINT PROGRAMMING FOR COMBINATORIAL OPTIMIZATION PROBLEMS, 2008, 5015 : 283 - 287
  • [8] An NC algorithm for minimum cuts
    Karger, DR
    Motwani, R
    SIAM JOURNAL ON COMPUTING, 1997, 26 (01) : 255 - 272
  • [9] Multicriteria global minimum cuts
    Armon, Amitai
    Zwick, Uri
    ALGORITHMICA, 2006, 46 (01) : 15 - 26
  • [10] MINIMUM CUTS IN SURFACE GRAPHS
    Chambers, Erin W.
    Erickson, Jeff
    Fox, Kyle
    Nayyeri, Amir
    SIAM JOURNAL ON COMPUTING, 2023, 52 (01) : 156 - 195