License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.59
URN: urn:nbn:de:0030-drops-129255
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12925/
Go to the corresponding LIPIcs Volume Portal

Henzinger, Monika ; Noe, Alexander ; Schulz, Christian ; Strash, Darren

Finding All Global Minimum Cuts in Practice

pdf-format:
LIPIcs-ESA-2020-59.pdf (0.7 MB)

Abstract

We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.

BibTeX - Entry

@InProceedings{henzinger_et_al:LIPIcs:2020:12925,
  author =	{Monika Henzinger and Alexander Noe and Christian Schulz and Darren Strash},
  title =	{{Finding All Global Minimum Cuts in Practice}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{59:1--59:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12925},
  URN =		{urn:nbn:de:0030-drops-129255},
  doi =		{10.4230/LIPIcs.ESA.2020.59},
  annote =	{Keywords: Minimum Cut, Graph Algorithm, Algorithm Engineering, Cut Enumeration, Balanced Cut, Global Minimum Cut, Large-scale Graph Analysis}
}

Keywords: Minimum Cut, Graph Algorithm, Algorithm Engineering, Cut Enumeration, Balanced Cut, Global Minimum Cut, Large-scale Graph Analysis
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: https://github.com/VieCut/VieCut

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI