A fast algorithm for optimally increasing the edge-connectivity

An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity λ) is considered. Given an input parameter δ, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by δ. A solution to this problem that runs in time O(δ²nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every δ´, 1⩽δ´⩽δ, in the same time bound. A modification of the solution solves the problem without knowing δ in advance. If δ=1, then the solution is particularly simple, running in O(nm) time, and it is a natural generalization of an algorithm of K. Eswaran and R.E. Tarjan (1976) for the case in which λ+δ=2. The converse problem (given an input number k, increase the connectivity of G as much as possible by adding at most k edges) is solved in the same time bound. The solution makes extensive use of the structure of particular sets of cuts