Next:
GT47 SHORTEST PATH
Up:
Miscellaneous
Previous:
Miscellaneous
-
I
NSTANCE
:
Graph
and a collection
of pairs of vertices from
V
.
-
S
OLUTION
:
A simple path in
G
that contains at most one vertex from each pair in
C
.
-
M
EASURE
:
Length of the path, i.e., the number of edges in the path.
-
Bad News:
NPO PB-complete [
49
].
-
Comment:
Transformation from L
ONGEST
C
OMPUTATION
.
-
Garey and Johnson:
GT54
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997