Next: MINIMUM BICONNECTIVITY AUGMENTATION
Up: Cuts and Connectivity
Previous: MINIMUM K-VERTEX CONNECTED SUBGRAPH
  Index
- INSTANCE:
Graph
.
k is a constant,
.
- SOLUTION:
A k-edge connected spanning subgraph
for G,
i.e. a spanning subgraph that cannot be disconnected by removing fewer
than k edges.
- MEASURE:
The cardinality of the spanning subgraph, i.e., |E'|.
- Good News:
Approximable within 1.704
[295], [101] and [149].
- Bad News:
APX-complete even for k=2 [149].
- Comment:
Approximable within
for even k
and within
for odd k
[101] and [149].
On directed graphs the problem is approximable within 1.61 for k=1
[300], within 2 for
,
and within
for
[101].
Variation in which each edge has a nonnegative weight and the
objective is to minimize the total weight of the spanning subgraph is
approximable within 2 for every k [303].
Viggo Kann
1999-04-22