Title: Fully Dynamic c-Edge Connectivity in Subpolynomial Time.
Abstract: 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(\sqrt{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.
Publication Year: 2020
Publication Date: 2020-04-16
Language: en
Type: preprint
Access and Citation
Cited By Count: 10
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot