Next: LONGEST PATH
Up: Routing Problems
Previous: MINIMUM K-STACKER CRANE PROBLEM
for each ,
A cycle in G that visits each vertex in V' exactly once and traverses
each edge in E'.
The total length of the cycle.
- Good News:
Approximable within 3/2 .
The special case where E' spans V is called the rural postman problem.
- Garey and Johnson: Generalization of ND27