Next:
ND46 MINIMUM SINGLE-SINK
Up:
Flow Problems
Previous:
ND44 MAXIMUM DISJOINT
-
I
NSTANCE
:
Graph
, length function
, and a
pair of vertices
s,t
in
V
.
-
S
OLUTION
:
Two vertex disjoint paths in
G
connecting
and
t
, i.e. two
sequences of vertices
and
such that
,
,
,
, and
are included in
E
,
and for any
i
,
and
are included in
E
.
-
M
EASURE
:
The longest of the two paths, i.e.
.
-
Good News:
Approximable within 2 [
254
].
-
Comment:
Approximable within 2 also if the paths should be
edge disjoint
instead of vertex disjoint.
Variation in which the graph is directed and we look for two vertex (edge)
disjoint directed paths is also approximable within 2, and is not
approximable within
for any
[
254
].
-
Garey and Johnson:
Similar to ND41
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997