Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Chinese postman problem
open-in-new
<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> and <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a>, Guan's route problem, the Chinese postman problem, postman tour or route inspection problem is to find a shortest closed path or circuit that visits every edge of an (connected) <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> at least once. When the graph has an <a href="/facts/Eulerian_circuit/4l2G67c7">Eulerian circuit</a> (a closed walk that covers every edge once), that circuit is an optimal solution. Otherwise, the <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> is to find the smallest number of graph edges to duplicate (or the subset of edges with the minimum possible total weight) so that the resulting <a href="/facts/Multigraph/udmS0Cp0">multigraph</a> does have an Eulerian circuit. It can be solved in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>, unlike the <a href="/facts/Travelling_salesman_problem/2WEKVLnV">Travelling Salesman Problem</a> which is <a href="/facts/NP-hardness/mQeNPv4R">NP-hard</a>. It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes and does not have to visit every edge. </p><p>The problem was originally studied by the Chinese mathematician <a href="/facts/Meigu_Guan/Yy0K2hzW">Meigu Guan</a> in 1960, whose Chinese paper was translated into English in 1962. The original name "Chinese postman problem" was coined in his honor; different sources credit the coinage either to <a href="/facts/Alan_J._Goldman/mYxtaGTf">Alan J. Goldman</a> or <a href="/facts/Jack_Edmonds/4bLnep3e">Jack Edmonds</a>, both of whom were at the <a href="/facts/NIST/gr9Fnh85">U.S. National Bureau of Standards</a> at the time. </p><p>A generalization takes as input any set <i>T</i> of evenly many vertices, and must produce as output a minimum-weight edge set in the graph whose odd-degree vertices are precisely those of <i>T</i>. This output is called a <i>T</i>-join. This problem, the <i>T</i>-join problem, is also solvable in polynomial time by the same approach that solves the postman problem. </p>