Fully Dynamic c-Edge Connectivity in Subpolynomial Time
share
We present a deterministic fully dynamic algorithm for c-edge connectivity problem with n^o(1) worst case update and query time for any positive integer c = (log n)^o(1) for a graph with n vertices. Previously, only polylogarithmic, O(√(n)), and O(n^2/3) worst case update time algorithms were known for fully dynamic 1, 2 and 3-edge connectivity problems respectively. Our techniques include a multi-level c-edge connectivity sparsifier, an online-batch update algorithm for the sparsifier, and a general approach to turn an online-batch dynamic algorithm with small amortized update time into a fully dynamic algorithm with worst case update time.
READ FULL TEXT