Next: MINIMUM K-CHINESE POSTMAN PROBLEM
Up: Routing Problems
Previous: MINIMUM METRIC BOTTLENECK WANDERING
  Index
- INSTANCE:
Mixed graph
,
length
for each .
- SOLUTION:
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.
- MEASURE:
The total length of the cycle.
- Good News:
Approximable within 3/2 [413].
- Garey and Johnson: ND25
Viggo Kann
2000-03-20