We give improved randomized (Monte Carlo) algorithms for undirected edge sp
litting and edge connectivity augmentation problems. Our algorithms run in
time (O) over tilde(n(2)) on n-vertex graphs, making, them an <(Omega)over
tilde>(m/n) factor faster than the best known deterministic ones on m-edge
graphs. (C) 2000 Academic Press.