Publication
Mathematical Programming
Paper

Matching, Euler tours and the Chinese postman

View publication

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 general b-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed. © 1973 The Mathematical Programming Society.

Date

Publication

Mathematical Programming

Authors

Share