Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.20137 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We present a framework for dynamically maintaining $k$-edge-connectivity of an undirected simple graph $G$ under edge insertions and deletions, where $k$ is a fixed constant. After an edge insertion, the algorithm identifies and removes a distinct redundant edge to maintain sparsity, in $O(k \log n)$ amortized time. After an edge deletion that reduces $λ(G)$ below $k$, the algorithm restores $k$-edge-connectivity by adding at most two new edges (excluding the deleted edge), in $O(k^{3/2} n^{3/2})$ time. The insertion procedure combines Nagamochi-Ibaraki sparse certificates with Link-Cut Trees; the deletion procedure uses a single maximum-flow computation on the sparsified graph. Throughout all updates, the graph is maintained with $O(kn)$ edges.