Next: LONGEST PATH Up: Routing Problems Previous: MINIMUM K-STACKER CRANE PROBLEM Index

### MINIMUM GENERAL ROUTING

- 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