Fully-dynamic min-cut

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.

Authors

• Mikkel Thorup

Keywords

No keywords are indexed for this paper.