(classic problem)
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.
Author: CRC-A
Kwan Mei-Ko, Graphic Programming Using Odd or Even Points, Chinese Math., 1:273-277, 1962.
Historical Note
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 Black.
Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "Chinese postman problem", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/chinesePostman.html