---
_id: '11657'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Alexander
  full_name: Noe, Alexander
  last_name: Noe
- first_name: Christian
  full_name: Schulz, Christian
  last_name: Schulz
- first_name: Darren
  full_name: Strash, Darren
  last_name: Strash
citation:
  ama: Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms.
    <i>ACM Journal of Experimental Algorithmics</i>. 2018;23:1-22. doi:<a href="https://doi.org/10.1145/3274662">10.1145/3274662</a>
  apa: Henzinger, M. H., Noe, A., Schulz, C., &#38; Strash, D. (2018). Practical minimum
    cut algorithms. <i>ACM Journal of Experimental Algorithmics</i>. Association for
    Computing Machinery. <a href="https://doi.org/10.1145/3274662">https://doi.org/10.1145/3274662</a>
  chicago: Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash.
    “Practical Minimum Cut Algorithms.” <i>ACM Journal of Experimental Algorithmics</i>.
    Association for Computing Machinery, 2018. <a href="https://doi.org/10.1145/3274662">https://doi.org/10.1145/3274662</a>.
  ieee: M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut
    algorithms,” <i>ACM Journal of Experimental Algorithmics</i>, vol. 23. Association
    for Computing Machinery, pp. 1–22, 2018.
  ista: Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms.
    ACM Journal of Experimental Algorithmics. 23, 1–22.
  mla: Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” <i>ACM Journal
    of Experimental Algorithmics</i>, vol. 23, Association for Computing Machinery,
    2018, pp. 1–22, doi:<a href="https://doi.org/10.1145/3274662">10.1145/3274662</a>.
  short: M.H. Henzinger, A. Noe, C. Schulz, D. Strash, ACM Journal of Experimental
    Algorithmics 23 (2018) 1–22.
date_created: 2022-07-27T08:28:26Z
date_published: 2018-10-01T00:00:00Z
date_updated: 2022-09-09T11:32:52Z
day: '01'
doi: 10.1145/3274662
extern: '1'
external_id:
  arxiv:
  - '1708.06127'
intvolume: '        23'
keyword:
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1708.06127
month: '10'
oa: 1
oa_version: Preprint
page: 1-22
publication: ACM Journal of Experimental Algorithmics
publication_identifier:
  eissn:
  - 1084-6654
  issn:
  - 1084-6654
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical minimum cut algorithms
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2018'
...