Definition: Find a minimum length closed walk that traverses each edge at least once. Finding an optimal solution in a graph with both directed and undirected edges is NP-complete.
See also Hamiltonian cycle, Euler cycle, traveling salesman, vehicle routing problem, optimization problem.
Note: This is similar to finding the most efficient way to route garbage trucks, school buses, etc. A good algorithm is given in Jack Edmonds and Ellis L. Johnson, Matching, Euler Tours, and the Chinese Postman, Mathematical Programming, 5:88-124, 1973.
From Algorithms and Theory of Computation Handbook, page 6-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Kwan Mei-Ko, Graphic Programming Using Odd or Even Points, Chinese Math., 1:273-277, 1962.
Kwan's article referred to optimizing a postman's route, was written by a Chinese author, and appeared in a Chinese math journal. Based on this Alan J. Goldman suggested the name "Chinese Postman problem" to Jack Edmonds when Edmonds was in Goldman's Operations Research group at the U.S. National Bureau of Standards (now NIST). Edmonds appreciated its "catchiness" and adopted it. Goldman was also indirectly influenced by recalling an Ellery Queen mystery named "The Chinese Orange Mystery". (Alan J. Goldman, personal communication, 14 December 2003)
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 23 February 2010.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Chinese postman problem", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 23 February 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/chinesePostman.html