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 条
  • [31] Parallel Minimum Cuts in Near-linear Work and Low Depth
    Geissmann, Barbara
    Gianinazzi, Lukas
    SPAA'18: PROCEEDINGS OF THE 30TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, 2018, : 1 - 11
  • [32] Policy-Compliant Maximum Network Flows
    Audenaert, Pieter
    Colle, Didier
    Pickavet, Mario
    APPLIED SCIENCES-BASEL, 2019, 9 (05):
  • [33] On the Uncertainty and Changeability of the Estimates of Seasonal Maximum Flows
    Markiewicz, Iwona
    Bogdanowicz, Ewa
    Kochanek, Krzysztof
    WATER, 2020, 12 (03)
  • [34] UNIFYING MAXIMUM CUT AND MINIMUM CUT OF A PLANAR GRAPH
    SHIH, WK
    WU, S
    KUO, YS
    IEEE TRANSACTIONS ON COMPUTERS, 1990, 39 (05) : 694 - 697
  • [35] TOWARDS AN OPTIMIZATION THEORY FOR DEFORMING DENSE GRANULAR MATERIALS: MINIMUM COST MAXIMUM FLOW SOLUTIONS
    Lin, Qun
    Tordesillas, Antoinette
    JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION, 2014, 10 (01) : 337 - 362
  • [36] A new-old algorithm for minimum-cut and maximum-flow in closure graphs
    Hochbaum, DS
    NETWORKS, 2001, 37 (04) : 171 - 193
  • [37] Maximum a posteriori X-ray computed tomography using graph cuts
    Maeda, Shin-ichi
    Fukuda, Wataru
    Kanemura, Atsunori
    Ishii, Shin
    INTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2010 (IW-SMI 2010), 2010, 233
  • [38] Maximum flows in parametric dynamic networks with lower bounds
    Avesalon, Nicoleta
    ANNALS OF THE UNIVERSITY OF CRAIOVA-MATHEMATICS AND COMPUTER SCIENCE SERIES, 2016, 43 (02): : 188 - 199
  • [39] Maximum Flows in Planar Dynamic Networks with Lower Bounds
    Schiopu, Camelia
    Ciurea, Eleonor
    FUNDAMENTA INFORMATICAE, 2018, 163 (02) : 189 - 204
  • [40] Constructing a cactus for minimum cuts of a graph in O (mn+n2 log n) time and O(m) Space
    Nagamochi, H
    Nakamura, S
    Ishii, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2003, E86D (02): : 179 - 185