{"ID":2883639,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.07783","arxiv_id":"2508.07783","title":"Simple Algorithms for Fully Dynamic Edge Connectivity","abstract":"In the fully dynamic edge connectivity problem, the input is a simple graph $G$ undergoing edge insertions and deletions, and the goal is to maintain its edge connectivity, denoted $λ_G$. We present two simple randomized algorithms solving this problem. The first algorithm maintains the edge connectivity in worst-case update time $\\tilde{O}(n)$ per edge update, matching the known bound but with simpler analysis. Our second algorithm achieves worst-case update time $\\tilde{O}(n/λ_G)$ and worst-case query time $\\tilde{O}(n^2/λ_G^2)$, which is the first algorithm with worst-case update and query time $o(n)$ for large edge connectivity, namely, $λ_G = ω(\\sqrt{n})$.","short_abstract":"In the fully dynamic edge connectivity problem, the input is a simple graph $G$ undergoing edge insertions and deletions, and the goal is to maintain its edge connectivity, denoted $λ_G$. We present two simple randomized algorithms solving this problem. The first algorithm maintains the edge connectivity in worst-case...","url_abs":"https://arxiv.org/abs/2508.07783","url_pdf":"https://arxiv.org/pdf/2508.07783v2","authors":"[\"Yotam Kenneth-Mordoch\",\"Robert Krauthgamer\"]","published":"2025-08-11T09:14:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}