Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2024 | 10.1137/1.9781611977042.2 | Workshop on Algorithm Engineering and Experimentation (ALENEX) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Monika Rauch Henzinger | 1 | 4307 | 481.86 |
| Alexander Noe | 2 | 17 | 3.35 |
| Christian Schulz | 3 | 240 | 24.10 |