Recent development of graph connectivity augmentation algorithms

The connectivity augmentation problem asks to add to a given graph the smal lest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensivel y studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, w e show how the minimum cut algorithm due to Nagamochi and Ibaraki is effect ively applied to solve the edge-connectivity augmentation problem.