Next: MINIMUM K-STACKER CRANE PROBLEM
Up: Routing Problems
Previous: MINIMUM K-CHINESE POSTMAN PROBLEM
  Index
- INSTANCE:
Mixed graph
,
length
for each
such
that for every arc there is a parallel edge of no greater length.
- SOLUTION:
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.
- MEASURE:
The total length of the cycle.
- Good News:
Approximable within 9/5 [171].
- Garey and Johnson: ND26
Viggo Kann
2000-03-20