arXiv Open Access 2021

Practical Fully Dynamic Minimum Cut Algorithms

Monika Henzinger Alexander Noe Christian Schulz

Lihat Sumber

Abstrak

We present a practically efficient algorithm for maintaining a global minimum cut in large dynamic graphs under both edge insertions and deletions. While there has been theoretical work on this problem, our algorithm is the first implementation of a fully-dynamic algorithm. The algorithm uses the theoretical foundation and combines it with efficient and finely-tuned implementations to give an algorithm that can maintain the global minimum cut of a graph with rapid update times. We show that our algorithm gives up to multiple orders of magnitude speedup compared to static approaches both on edge insertions and deletions.

Topik & Kata Kunci

cs.DS

Penulis (3)

Monika Henzinger

Alexander Noe

Christian Schulz

Format Sitasi

APA MLA BibTeX

Henzinger, M., Noe, A., Schulz, C. (2021). Practical Fully Dynamic Minimum Cut Algorithms. https://arxiv.org/abs/2101.05033

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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