Fully-dynamic min-cut
Mikkel Thorup · 2001
We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in \tilde O(\sqrt{n}) time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^{2/3}), dating back to FOCS'92.