Connectivity Augmentation of Graphs

We consider the general problem of determining a smallest set of edges which must be added to a given graph (hyper graph, digraph)in order to make it k-edge-connected (k-vertex-connected). We give a short summary of those cases of the augmentation problems which have been solved by polynomial algorithms and min-max formulae. We then describe some recent progress we have made on the vertex-connectivity augmentation problem for undirected graphs.