Next: MINIMUM STRONG CONNECTIVITY AUGMENTATION Up: Cuts and Connectivity Previous: MINIMUM K-EDGE CONNECTED SUBGRAPH Index

### MINIMUM BICONNECTIVITY AUGMENTATION

- INSTANCE: Graph and a symmetric weight function .

- SOLUTION: A connectivity augmenting set E' for G, i.e., a set E' of unordered pairs of vertices from V such that is biconnected.

- MEASURE: The weight of the augmenting set, i.e., .

- Good News: Approximable within 2 [160] and [302].

- Comment: The same bound is valid also when G' must be bridge connected (edge connected) [302]. Minimum k-Connectivity Augmentation, the problem in which G' has to be k-connected (vertex or edge connected), is also approximable within 2 [293]. If the weight function satisfies the triangle inequality, the problem is approximable within 3/2 [161]. Variation in which G is planar and the augmentation must be planar is approximable within 5/3 in the unweighted case (where w(u,v)=1) [153]. If the problem is the same as weighted MINIMUM K-VERTEX CONNECTED SUBGRAPH.

- Garey and Johnson: ND18