Next: LONGEST PATH
Up: Routing Problems
Previous: MINIMUM K-STACKER CRANE PROBLEM
  Index
- INSTANCE:
Graph
,
length
for each ,
subset
,
subset .
- SOLUTION:
A cycle in G that visits each vertex in V' exactly once and traverses
each edge in E'.
- MEASURE:
The total length of the cycle.
- Good News:
Approximable within 3/2 [269].
- Comment:
The special case where E' spans V is called the rural postman problem.
- Garey and Johnson: Generalization of ND27
Viggo Kann
2000-03-20