Next: MINIMUM SINGLE-SINK EDGE INSTALLATION
Up: Flow Problems
Previous: MAXIMUM DISJOINT CONNECTING PATHS
pair of vertices s,t in V.
Two vertex disjoint paths in G connecting s and t, i.e. two
sequences of vertices
are included in E,
and for any i,
are included in E.
The longest of the two paths, i.e.
- Good News:
Approximable within 2 .
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
- Garey and Johnson: Similar to ND41