Parallel and fast sequential algorithms for undirected edge connectivity augmentation

by András A. Benczúr

Math. Prog. B 84(3):595--640 ps.gz ps pdf

Augmenting edge connectivity in ~O(n^3) time

Proc. 26th Annual Symp. on Theory of Comp. (1994) ps.gz, ps, ps.gz, no figures ps, no figures pdf

This is a mostly outdated conference version. I no longer feel responsible for bugs; read the full paper

Versions of the document #1 and #2 in Citeseer database

Reference in context as in the Hypertext Bibliography Project (apparently not maintained since 1998)

Abstract

In the edge connectivity augmentation problem one wants to find an edge set of minimum total capacity that increases the edge connectivity of a given undirected graph by T. It is a known non-trivial property of the edge connectivity augmentation problem that there is a sequence of e dge sets E_1,E_2,... that UE_i optmially increases the connectivity by T, for any integer T. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E_i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augm entation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs.

Related articles

Citations

1. András Frank
   Connectivity augmentation problems in network design
   Updated version of Mathematical Programming: The state of the art
2. Jorgen Bang-Jensen and Tibor Jordán
   Edge-connectivity augmentation preserving simplicity
   38th Annual Symposium on Foundations of Computer Science, pages 486-495, Miami Beach, Florida, 20-22 October 1997.
3. Dinitz Y, Vainshtein A
   The general structure of edge-connectivity of a vertex subset in a graph and its incremental maintenance. Odd case
   SIAM J COMPUT 30: (3) 753-808 AUG 24 2000
4. Nagamochi H, Nakao Y, Ibaraki T
   A fast algorithm for cactus representations of minimum cuts
   JPN J IND APPL MATH 17: (2) 245-264 JUN 2000
5. Dinitz Y, Nossenson R
   Incremental maintenance of the 5-edge-connectivity classes of a graph
   LECT NOTES COMPUT SC 1851: 272-285 2000
6. Nagamochi H
   Recent development of graph connectivity augmentation algorithms
   IEICE T INF SYST E83D: (3) 372-383 MAR 2000
7. T. Hsu
   Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation
   Proc. 6th ISAAC (1995)
8. Yefim Dinitz and Zeev Nutov
   A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance
   Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pages 509-518, Las Vegas, Nevada, 29 May-1 June 1995.
9. Harold N. Gabow
   Efficient splitting off algorithms for graphs
   Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 696-705, Montréal, Québec, Canada, 23-25 May 1994.
10. David R. Karger and Clifford Stein
    A new approach to the minimum cut problem
    Journal of the ACM, 43(4):601-640, July 1996.
11. Hiroshi Nagamochi and Toshihide Ibaraki
    Deterministic O (nm) time edge-splitting in undirected graphs
    Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 64-73, Philadelphia, Pennsylvania, 22-24 May 1996.
12. Hiroshi Nagamochi, Takashi Shiraki, and Toshihide Ibaraki
    Computing edge-connectivity augmentation function in O (nm) time
    Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 649-658, New Orleans, Louisiana, 5-7 January 1997.
13. Hiroshi Nagamochi and Toshihide Ibaraki
    Augmenting Edge-Connectivity over the Entire Range in O (nm) time
    Journal of Algorithms 30, pp. 253--301 (1999)