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 connectivity 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 increases the connectivity by tau, for any integer tau. 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) augmentation 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.
edge connectivity hypergraphs graph augmentation randomized algorithms parallel algorithms combinatorial optimization