Next:
GT48 MINIMUM POINT-TO-POINT
Up:
Miscellaneous
Previous:
GT46 LONGEST PATH
-
I
NSTANCE
:
Graph
, a collection
of
pairs of vertices from
V
, an initial vertex
, and a final vertex
.
-
S
OLUTION
:
A simple path from
to
f
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 [
202
].
-
Comment:
Transformation from S
HORTEST
C
OMPUTATION
.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997