Next:
ND37 MINIMUM K-STACKER
Up:
Routing Problems
Previous:
ND35 MINIMUM K-CHINESE
-
I
NSTANCE
:
Mixed graph
, length
for each
such
that for every arc there is a parallel edge of no greater length.
-
S
OLUTION
:
A cycle in
G
(possibly containing repeated vertices) that includes each
directed edge in
A
at least once, traversing such edges only in the
specified direction.
-
M
EASURE
:
The total length of the cycle.
-
Good News:
Approximable within 9/5 [
112
].
-
Garey and Johnson:
ND26
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997