Definition:Chinese Postman Problem

Definition

A Chinese postman problem is a problem in network theory equivalent to that of a postman who needs to:

visit all streets in an area to deliver letters

return to the starting point

covering the least possible distance.

Hence it is equivalent to finding a closed walk in a weighted graph which includes every edge with least total weight.

Also see

• Traveling Salesman Problem

• Results about Chinese postman problems can be found here.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Chinese postman problem
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Chinese postman problem