Chinese Postman Problem

A problem asking for the shortest tour of a graph which visits each edge at least once (Kwan 1962; Skiena 1990, p. 194). For an Eulerian graph, an Eulerian cycle is the optimal solution. In a tree, however, the path crosses each edge twice.

See also

Eulerian Cycle, Traveling Salesman Problem

Explore with Wolfram|Alpha


Edmonds, J. and Johnson, E. L. "Matching, Euler Tours, and the Chinese Postman." Math. Programm. 5, 88-124, 1973.Kwan, M. K. "Graphic Programming Using Odd or Even Points." Chinese Math. 1, 273-277, 1962.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Referenced on Wolfram|Alpha

Chinese Postman Problem

Cite this as:

Weisstein, Eric W. "Chinese Postman Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications