Next: MINIMUM BOUNDED DIAMETER AUGMENTATION Up: Cuts and Connectivity Previous: MINIMUM BICONNECTIVITY AUGMENTATION Index

### MINIMUM STRONG CONNECTIVITY AUGMENTATION

- INSTANCE: Directed graph and a weight function .

- SOLUTION: A connectivity augmenting set A' for G, i.e., a set A' of ordered pairs of vertices from V such that is strongly connected.

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

- Good News: Approximable within 2 [160].

- Comment: The unweighted problem (i.e. where all weights are 1) is approximable within 1.61 [300].

- Garey and Johnson: ND19