Parallel and fast sequential algorithms for undirected edge connectivity augmentation

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 tau. It is a known non-trivial property of the edge con nectivity augmentation problem that there is a sequence of edge sets E-1, E -2,..., such that boolean OR(i)less than or equal to E-i optmially increase s the connectivity by tau, for any integer tau. The main result of the pape r is that this sequence of edge sets can be divided into O(n) groups such t hat 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) augmentation algorithm. We also present ne w efficient subroutines for finding the so-called extreme sets and the cact us representation of min-cuts required in our algorithms. Augmenting the co nnectivity of hypergraphs with ordinary edges is known to be structurally h arder than that of ordinary graphs. In a weaker version when one exceptiona l hyperedge is allowed in the augmenting edge set, we derive similar result s as for ordinary graphs.