Home
Blog
Publications
Light
Dark
Automatic
Graphs
Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice
We prove impossibility results showing that Karger’s contraction algorithm cannot be extended to $s$-$t$-mincuts or normalized cuts. However, we show how extensions of Karger’s algorithm can still be useful for seeded segmentation.
Erik Jenner
,
Enrique Fita Sanmartín
,
Fred A. Hamprecht
PDF
Cite
Code
Trading off speed against the probability of success in the Karger-Stein Algorithm
The Karger-Stein algorithm is an improvement over Karger’s beautiful contraction algorithm for minimum graph cuts. In this post, I show how it finds the perfect tradeoff between finding a mincut with high probability and finding it quickly. In the course of doing so, we will also understand where the somewhat opaque factor of sqrt(2) comes from.
Dec 6, 2020
7 min read
Cite
×