Next: MINIMUM K-CHINESE POSTMAN PROBLEM Up: Routing Problems Previous: MINIMUM METRIC BOTTLENECK WANDERING Index

### MINIMUM CHINESE POSTMAN FOR MIXED GRAPHS

- INSTANCE: Mixed graph , length for each .

- SOLUTION: A cycle in G (possibly containing repeated vertices) that includes each directed and undirected edge at least once, traversing directed edges only in the specified direction.

- MEASURE: The total length of the cycle.

- Good News: Approximable within 5/3 [158].

- Comment: Approximable within 3/2 for planar graphs [158].

- Garey and Johnson: ND25