A unifying augmentation algorithm for two-edge connectivity and biconnectivity

Given an undirected graph G and two vertex subsets H-1 and H-2, the bi-leve l augmentation problem is that of adding to G the smallest number of edges such that the resulting graph contains two internally vertex-disjoint paths between every pair of vertices in H-1 and two edge-disjoint paths between every pair of vertices in H-2. We present an algorithm to solve this proble m in linear time. By properly setting H-1 and H-2, this augmentation algori thm subsumes existing optimal algorithms for several graph augmentation pro blems.