Quadratic-time Algorithms for Edge-Connectivity Augmentation and
Splitting Off
by András A. Benczúr and
David R. Karger
J. Alg 37(1), pp. 2-36 (2000)
ps.gz
ps
pdf
Augmenting undirected edge-connectivity in ~O(n^2) time
The preliminary conference version
Proc. of the 9th Annual ACM-SIAM Symp. on Discrete Algorithms (1998)
ps.gz
ps
pdf
Document
in the
Citeseer database
Citations from the paper
as in the Hypertext
Bibliography Project (apparently not maintained since 1998)
Related articles
My FOCS 94/Math Prog 99 paper has weaker
results in general but the two papers are incomparable in certain aspects.
Citations
- G. Even, J. Feldman, G. Kortsarz and Z. Nutov,
A 3/2-approximation for augmenting a connected graph into a
two-connected graph
Approx 2001, pages 90--101
- Fleischer L
Building chain and cactus representations of all minimum cuts from
Hao-Orlin in the same asymptotic run time
J ALGORITHM 33: (1) 51-72 OCT 1999
- Schwarz S, Krumke SO
On budget-constrained flow improvement
INFORM PROCESS LETT 66: (6) 291-297 JUN 30 1998
- Nagamochi H
Recent development of graph connectivity augmentation algorithms
IEICE T INF SYST E83D: (3) 372-383 MAR 2000