Minimum

作     者：John H. Reif 

出 版 物：《SIAM Journal on Computing》 

年 卷 期：1983年第12卷第1期

页      面：71-81页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：planar network minimum - cut graph algorithm 

摘      要：Let N be a planar undirected network with distinguished vertices s, t, a total of n vertices, and each edge labeled with a positive real (the edge’s cost) from a set L. This paper presents an algorithm for computing a minimum (cost) s-t cut of N. For general L, this algorithm runs in time O(nlog2(n)) role=presentationO(nlogspan style=display: inline-block; width: