Back to Search
Start Over
Augmenting Undirected Edge Connectivity in Õ(n2) Time
- Source :
- Journal of Algorithms; October 2000, Vol. 37 Issue: 1 p2-36, 35p
- Publication Year :
- 2000
-
Abstract
- We give improved randomized (Monte Carlo) algorithms for undirected edge splitting and edge connectivity augmentation problems. Our algorithms run in time Õ(n2) on n-vertex graphs, making them an Ω̃(m/n) factor faster than the best known deterministic ones on m-edge graphs.
Details
- Language :
- English
- ISSN :
- 01966774 and 10902678
- Volume :
- 37
- Issue :
- 1
- Database :
- Supplemental Index
- Journal :
- Journal of Algorithms
- Publication Type :
- Periodical
- Accession number :
- ejs782958
- Full Text :
- https://doi.org/10.1006/jagm.2000.1093