Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice

Erik Jenner, Enrique Fita Sanmartín, Fred A. Hamprecht

The minimum graph cut and minimum $s$-$t$-cut problems are important primitives in the modeling of combinatorial problems in computer science, including in computer vision and mach…