Augmenting undirected edge connectivity in O(n(2)) time

Authors
Benczur, AA Karger, DR
Citation
Aa. Benczur et Dr. Karger, Augmenting undirected edge connectivity in O(n(2)) time, J ALGORITHM, 37(1), 2000, pp. 2-36
Citations number
28
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF ALGORITHMS
ISSN journal
01966774 → ACNP
Volume
37
Issue
1
Year of publication
2000
Pages
2 - 36
Database
ISI
SICI code
0196-6774(200010)37:1<2:AUECIO>2.0.ZU;2-J
Abstract
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.