Skip to content

Latest commit

 

History

History
19 lines (11 loc) · 1.46 KB

README.md

File metadata and controls

19 lines (11 loc) · 1.46 KB
Raw

Min-Cut Algorithm

An implementation of Karger's Min-Cut Algorithm and Karger-Stein Algorithm.

The example is from the open course on Coursera named Algorithms: Design and Analysis, Part 1 by Prof. Tim Roughgarden

It may have some difference compared with the assignment online, please check the algorithm carefully.

About the algorithm:

The goal of the algorithm is to find a global min-cut in a graph in polynomial time. The graph is undirected and allows parallel edges. The algorithm chooses an edge randomly and contracts it. The procedure is performed recursively until two nodes remain.

Reference:

  • Karger, David R. "Global min-cuts in RNC, and other ramifications of a simple min-out algorithm." Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1993.

  • Stoer, Mechthild, and Frank Wagner. "A simple min-cut algorithm." Journal of the ACM (JACM) 44.4 (1997): 585-591.

  • Karger, David R., and Clifford Stein. "A new approach to the minimum cut problem." Journal of the ACM (JACM) 43.4 (1996): 601-640.

  • Karger, David R., and Debmalya Panigrahi. "A near-linear time algorithm for constructing a cactus representation of minimum cuts." Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2009.