---
_id: '11851'
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 weighted sum of the cut
    edges. In this paper, we engineer the fastest known exact algorithm for the problem.
    State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm
    of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce
    the graph size such that at least one minimum cut is maintained in the contracted
    graph. Our algorithm achieves improvements in running time over these algorithms
    by a multitude of techniques. First, we use a recently developed fast and parallel
    inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards,
    we use reductions that depend on this bound to reduce the size of the graph much
    faster than previously possible. We use improved data structures to further lower
    the running time of our algorithm. Additionally, we parallelize the contraction
    routines of Nagamochi et al. . Overall, we arrive at a system that significantly
    outperforms the fastest state-of-the-art solvers for the exact minimum cut problem.
article_number: '8820968'
article_processing_charge: No
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
citation:
  ama: 'Henzinger MH, Noe A, Schulz C. Shared-memory exact minimum cuts. In: <i>33rd
    International Parallel and Distributed Processing Symposium</i>. Institute of
    Electrical and Electronics Engineers; 2019. doi:<a href="https://doi.org/10.1109/ipdps.2019.00013">10.1109/ipdps.2019.00013</a>'
  apa: 'Henzinger, M. H., Noe, A., &#38; Schulz, C. (2019). Shared-memory exact minimum
    cuts. In <i>33rd International Parallel and Distributed Processing Symposium</i>.
    Rio de Janeiro, Brazil: Institute of Electrical and Electronics Engineers. <a
    href="https://doi.org/10.1109/ipdps.2019.00013">https://doi.org/10.1109/ipdps.2019.00013</a>'
  chicago: Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory
    Exact Minimum Cuts.” In <i>33rd International Parallel and Distributed Processing
    Symposium</i>. Institute of Electrical and Electronics Engineers, 2019. <a href="https://doi.org/10.1109/ipdps.2019.00013">https://doi.org/10.1109/ipdps.2019.00013</a>.
  ieee: M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory exact minimum cuts,”
    in <i>33rd International Parallel and Distributed Processing Symposium</i>, Rio
    de Janeiro, Brazil, 2019.
  ista: 'Henzinger MH, Noe A, Schulz C. 2019. Shared-memory exact minimum cuts. 33rd
    International Parallel and Distributed Processing Symposium. IPDPS: International
    Parallel and Distributed Processing Symposium, 8820968.'
  mla: Henzinger, Monika H., et al. “Shared-Memory Exact Minimum Cuts.” <i>33rd International
    Parallel and Distributed Processing Symposium</i>, 8820968, Institute of Electrical
    and Electronics Engineers, 2019, doi:<a href="https://doi.org/10.1109/ipdps.2019.00013">10.1109/ipdps.2019.00013</a>.
  short: M.H. Henzinger, A. Noe, C. Schulz, in:, 33rd International Parallel and Distributed
    Processing Symposium, Institute of Electrical and Electronics Engineers, 2019.
conference:
  end_date: 2019-05-24
  location: Rio de Janeiro, Brazil
  name: 'IPDPS: International Parallel and Distributed Processing Symposium'
  start_date: 2019-05-20
date_created: 2022-08-16T07:25:23Z
date_published: 2019-05-01T00:00:00Z
date_updated: 2023-02-21T16:30:34Z
day: '01'
doi: 10.1109/ipdps.2019.00013
extern: '1'
external_id:
  arxiv:
  - '1808.05458'
language:
- iso: eng
main_file_link:
- url: https://arxiv.org/abs/1808.05458
month: '05'
oa_version: Preprint
publication: 33rd International Parallel and Distributed Processing Symposium
publication_identifier:
  eisbn:
  - 978-1-7281-1246-6
  eissn:
  - 1530-2075
  isbn:
  - 978-1-7281-1247-3
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
related_material:
  record:
  - id: '11851'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Shared-memory exact minimum cuts
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...