MINIMUM CHINESE POSTMAN FOR MIXED GRAPHS

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

INSTANCE: Mixed graph $G=\left(V,A,E\right)$ , length $l(e)\in N$ for each $e\in A\cup E$ .
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 3/2 [413].
Garey and Johnson: ND25

Viggo Kann
2000-03-20