Matching, Euler tours and the Chinese postman

The solution of the Chinese postman problem using matching theory is given and the convex hull of integer solutions is described as a linear programming polyhedron, used to show that a good algorithm gives an optimum solution.

Abstract

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.