Next:
ND35 MINIMUM K-CHINESE
Up:
Routing Problems
Previous:
ND33 MINIMUM METRIC
-
I
NSTANCE
:
Mixed graph
, length
for each
.
-
S
OLUTION
:
A cycle in
G
(possibly containing repeated vertices) that includes each
directed and undirected edge at least once, traversing directed edges only
in the specified direction.
-
M
EASURE
:
The total length of the cycle.
-
Good News:
Approximable within 5/3 [
111
].
-
Comment:
Approximable within 3/2 for planar graphs [
111
].
-
Garey and Johnson:
ND25
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997