@article{11657,
  abstract     = {The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate.},
  author       = {Henzinger, Monika H and Noe, Alexander and Schulz, Christian and Strash, Darren},
  issn         = {1084-6654},
  journal      = {ACM Journal of Experimental Algorithmics},
  keywords     = {Theoretical Computer Science},
  pages        = {1--22},
  publisher    = {Association for Computing Machinery},
  title        = {{Practical minimum cut algorithms}},
  doi          = {10.1145/3274662},
  volume       = {23},
  year         = {2018},
}