Efficient Edge Splitting-Off Algorithms Maintaining All-Pairs Edge-Connectivities
Lap Chi Lau, Chun Kong Yung · SIAM Journal on Computing · 2013
We present new edge splitting-off results maintaining all-pairs edge-connectivities of an undirected graph. We first give an alternate proof of Mader's theorem, and use it to obtain a deterministic $\tilde{O}(m + {r_{\max}}^2 \cdot n^2)$-time complete edge splitting-off algorithm for unweighted graphs, where $r_{\max}$ denotes the maximum edge-connectivity requirement. This improves upon the best known algorithm by Gabow by a factor of $\tilde{\Omega}(n)$. We then prove a new structural property, and use it to further speed up the algorithm to obtain a randomized $\tilde{O}(m + {r_{\max}}^3 \cdot n)$-time algorithm. These edge splitting-off algorithms can be used directly to speed up various graph algorithms.