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 5/3 [158].
- Comment:
Approximable within 3/2 for planar graphs [158].
- Garey and Johnson: ND25
Viggo Kann
1999-04-22