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

  1. 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
  2. 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
  3. Schwarz S, Krumke SO
    On budget-constrained flow improvement
    INFORM PROCESS LETT 66: (6) 291-297 JUN 30 1998
  4. Nagamochi H
    Recent development of graph connectivity augmentation algorithms
    IEICE T INF SYST E83D: (3) 372-383 MAR 2000