arXiv Open Access 2020

Finding All Global Minimum Cuts In Practice

Monika Henzinger Alexander Noe Christian Schulz Darren Strash

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (4)

Monika Henzinger

Alexander Noe

Christian Schulz

Darren Strash

Format Sitasi

APA MLA BibTeX

Henzinger, M., Noe, A., Schulz, C., Strash, D. (2020). Finding All Global Minimum Cuts In Practice. https://arxiv.org/abs/2002.06948

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓