Simple Algorithms for Fully Dynamic Edge Connectivity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908601269878784 |
|---|---|
| author | Kenneth-Mordoch, Yotam Krauthgamer, Robert |
| author_facet | Kenneth-Mordoch, Yotam Krauthgamer, Robert |
| contents | 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})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_07783 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simple Algorithms for Fully Dynamic Edge Connectivity Kenneth-Mordoch, Yotam Krauthgamer, Robert Data Structures and Algorithms 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})$. |
| title | Simple Algorithms for Fully Dynamic Edge Connectivity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.07783 |