Augmenting graphs to meet edge-connectivity requirements

The problem of determining the minimum number γ of edges to be added to a graph G so that in the resulting graph the edge-connectivity between every pair {u,v} of nodes is at least a prescribed value r(u,v) is treated. A min-max formula for γ is derived, and a polynomial-time algorithm for computing γ is described. The directed counterpart of the problem is also solved for the case in which r(u,v)=k⩾1. The approach used makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge costs arise from node costs