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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
van Aardenne-Ehrenfest and N.G. de Bruijn, “Circuits and trees in oriented graphs”,Simon Stevin 28 (1951) 203–217.
E.J. Beltrami and L.D. Bodin, “Networks and vehicle routing for municipal waste collection”, Report No. UPS 72-18, State University of New York, Stony Brook, N.Y. (1972).
C. Berge,The theory of graphs and its applications (Wiley, New York, 1962).
J. Edmonds, “Paths, trees and flowers”,Canadian Journal of Mathematics 17 (1965) 449–467.
J. Edmonds, “Maximum matching and a polyhedron with 0, 1-vertices”,Journal of Research of the National Bureau of Standards Section B, 1, 2 (1965) 125–130.
J. Edmonds, “The Chinese postman problem”,Operations Research 13 Suppl. 1 (1965) 373.
J. Edmonds and E.L. Johnson, “Matching: a well-solved class of integer linear programs”, in:Combinatorial structures and their applications (Gordon and Breach, New York, 1970) 89–92.
J. Edmonds, E.L. Johnson and S. Lockhart, “Blossom I: a computer code for the matching problem”, to appear.
L. Euler, “Solutio problematis ad geometriam situs pertinentis”,Commentarii Academiae Petropolitanae 8 (1736) 128–140.
L.R. Ford Jr. and D.R. Fulkerson,Flows in networks (Princeton Univ. Press, Princeton, N.J., 1962).
A.J. Hoffman, “Some recent applications of the theory of linear inequalities to extremal combinatorial analysis”, in:Proceedings of Symposia on Applied Mathematics Vol. 10 (American Mathematical Society, Providence, R.I., 1960).
T.C. Hu, “Revised matrix algorithms for shortest paths in a network“,SIAM Journal 15 (1967) 207–218.
T.M. Liebling,Graphentheorie in Planungs- und Tourenproblemen, Lecture Notes in Operations Research and Mathematical Systems 21 (Springer, Berlin, 1970).
K. Mei-Ko, “Graphic programming using odd or even points”,Chinese Mathematics 1 (1962) 273–277.
C.S. Orloff, “Routing and scheduling a fleet of vehicles to/from central facilities — the school bus problem”, Ph. D. Thesis, Cornell University, Ithaca, N.Y. (1972).
R. Stricker, “Public sector vehicle routing: the Chinese postman problem”, Master Thesis, Massachusetts Institute of Technology, Cambridge, Mass. (August 1970).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Edmonds, J., Johnson, E.L. Matching, Euler tours and the Chinese postman. Mathematical Programming 5, 88–124 (1973). https://doi.org/10.1007/BF01580113
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580113