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.