Next: MINIMUM BOUNDED DIAMETER AUGMENTATION
Up: Cuts and Connectivity
Previous: MINIMUM BICONNECTIVITY AUGMENTATION
  Index
- 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 [172].
- Comment:
The unweighted problem (i.e. where all weights are 1) is approximable
within 1.61 [317].
- Garey and Johnson: ND19
Viggo Kann
2000-03-20