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 [254].
- Comment:
The special case where V'=V is called the rural postman problem.
- Garey and Johnson: Generalization of ND27
Viggo Kann
1999-04-22