Matching, Euler tours and the Chinese postman. (English) Zbl 0281.90073


90C35 Programming involving graphs or networks
90C10 Integer programming
Full Text: DOI


[1] van Aardenne-Ehrenfest and N.G. de Bruijn, ”Circuits and trees in oriented graphs”,Simon Stevin 28 (1951) 203–217. · Zbl 0044.38201
[2] 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). · Zbl 0284.90032
[3] C. Berge,The theory of graphs and its applications (Wiley, New York, 1962). · Zbl 0097.38903
[4] J. Edmonds, ”Paths, trees and flowers”,Canadian Journal of Mathematics 17 (1965) 449–467. · Zbl 0132.20903
[5] 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. · Zbl 0141.21802
[6] J. Edmonds, ”The Chinese postman problem”,Operations Research 13 Suppl. 1 (1965) 373. · Zbl 0132.20604
[7] 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. · Zbl 0258.90032
[8] J. Edmonds, E.L. Johnson and S. Lockhart, ”Blossom I: a computer code for the matching problem”, to appear.
[9] L. Euler, ”Solutio problematis ad geometriam situs pertinentis”,Commentarii Academiae Petropolitanae 8 (1736) 128–140.
[10] L.R. Ford Jr. and D.R. Fulkerson,Flows in networks (Princeton Univ. Press, Princeton, N.J., 1962). · Zbl 0106.34802
[11] 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). · Zbl 0096.00606
[12] T.C. Hu, ”Revised matrix algorithms for shortest paths in a network”,SIAM Journal 15 (1967) 207–218. · Zbl 0158.15404
[13] T.M. Liebling,Graphentheorie in Planungs- und Tourenproblemen, Lecture Notes in Operations Research and Mathematical Systems 21 (Springer, Berlin, 1970). · Zbl 0322.90022
[14] K. Mei-Ko, ”Graphic programming using odd or even points”,Chinese Mathematics 1 (1962) 273–277. · Zbl 0143.41904
[15] 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).
[16] R. Stricker, ”Public sector vehicle routing: the Chinese postman problem”, Master Thesis, Massachusetts Institute of Technology, Cambridge, Mass. (August 1970).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.