Augmenting undirected edge connectivity in Õ(n2) time
András A. Benczúr, David R. Karger · 1998
We give improved randomized (Monte Carlo) algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time ~ O(n^2) on n-vertex graphs, making them an ~\\Omega(m/n) factor faster than the best known deterministic ones on m-edge graphs.