Next:
ND28 MINIMUM BOUNDED
Up:
Cuts and Connectivity
Previous:
ND26 MINIMUM BICONNECTIVITY
-
I
NSTANCE
:
Directed graph
and a weight function
.
-
S
OLUTION
:
A connectivity augmenting set
A'
for
G
, i.e., a set
A'
of ordered
pairs of vertices from
V
such that
is
strongly connected.
-
M
EASURE
:
The weight of the augmenting set, i.e.,
.
-
Good News:
Approximable within 2 [
113
].
-
Comment:
The unweighted problem (i.e. where all weights are 1) is approximable
within 1.61 [
226
].
-
Garey and Johnson:
ND19
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997