7
全局最小割：Karger’s Min Cut Algorithm
source link: http://blog.kongfy.com/2015/02/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二月 2015
二月 2015 发表了 1 篇文章
全局最小割：Karger’s Min Cut Algorithm
Cut in an undirected graph
提到无向图的最小割问题，首先想到的就是Ford-Fulkerson算法解s-t最小割，通过Edmonds–Karp实现可以在O(nm2)时间内解决这个问题（n为图中的顶点数，m为图中的边数）。
但是全局最小割和s-t最小割不同，并没有给定的指定的源点s和汇点t，如果通过Ford-Fulkerson算法来解这一问题，则需要枚举汇点t（共n−1），时间复杂度为O(n2m2)。
Can we do better?
分类： 算法 | 2015-02-07 | 261 个字 | 2 Comments
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK