Chinese postman problem

Source: Wikipedia, the free encyclopedia.
A worked example of an undirected Chinese postman problem:
1 Each street must be traversed at least once, starting and ending at the post office at A.
2 Four vertices with odd degree (orange) are found on its equivalent graph.
3 The pairing with the lowest total length is found.
4 After corresponding edges are added (red), the length of the Eulerian circuit is found.

In

polynomial time,[2] unlike the Travelling Salesman Problem which is NP-hard.[3]
It is different from the Travelling Salesman Problem in that the travelling salesman cannot repeat visited nodes.

The problem was originally studied by the Chinese mathematician

U.S. National Bureau of Standards at the time.[5][6]

A generalization is to choose any set T of evenly many vertices that are to be joined by an edge set in the graph whose odd-degree vertices are precisely those of T. Such a set is called a T-join. This problem, the T-join problem, is also solvable in polynomial time by the same approach that solves the postman problem.

Undirected solution and T-joins

The undirected route inspection problem can be solved in

polynomial time by an algorithm
based on the concept of a T-join. Let T be a set of vertices in a graph. An edge set J is called a T-join if the collection of vertices that have an odd number of incident edges in J is exactly the set T. A T-join exists whenever every connected component of the graph contains an even number of vertices in T. The T-join problem is to find a T-join with the minimum possible number of edges or the minimum possible total weight.

For any T, a smallest T-join (when it exists) necessarily consists of paths that join the vertices of T in pairs. The paths will be such that the total length or total weight of all of them is as small as possible. In an optimal solution, no two of these paths will share any edge, but they may have shared vertices. A minimum T-join can be obtained by constructing a complete graph on the vertices of T, with edges that represent shortest paths in the given input graph, and then finding a minimum weight perfect matching in this complete graph. The edges of this matching represent paths in the original graph, whose union forms the desired T-join. Both constructing the complete graph, and then finding a matching in it, can be done in O(n3) computational steps.

For the route inspection problem, T should be chosen as the set of all odd-degree vertices. By the assumptions of the problem, the whole graph is connected (otherwise no tour exists), and by the

Euler tour, a tour that visits each edge of the multigraph exactly once. This tour will be an optimal solution to the route inspection problem.[7][2]

Directed solution

On a directed graph, the same general ideas apply, but different techniques must be used. If the directed graph is Eulerian, one need only find an Euler cycle. If it is not, one must find T-joins, which in this case entails finding paths from vertices with an in-

strongly connected.[2][8]

Applications

Various combinatorial problems have been reduced to the Chinese Postman Problem, including finding a maximum cut in a planar graph and a minimum-mean length circuit in an undirected graph.[9]

Variants

A few variants of the Chinese Postman Problem have been studied and shown to be

NP-complete.[10]

See also

References

  1. ISBN 9781420099829
  2. ^
    S2CID 15249924
  3. ^ "The Travelling Salesman Problem" (PDF).
  4. MR 0162630
    . Translated in Chinese Mathematics 1: 273–277, 1962.
  5. ^ Pieterse, Vreda; Black, Paul E., eds. (September 2, 2014), "Chinese postman problem", Dictionary of Algorithms and Data Structures, National Institute of Standards and Technology, retrieved 2016-04-26
  6. MR 2991468
    .
  7. ^ Lawler, E.L. (1976), Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston
  8. hdl:11059/14013
  9. ^ A. Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Volume A, Springer. (2002).
  10. ^ Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G, A compendium of NP optimization problems, KTH NADA, Stockholm, retrieved 2008-10-22
  11. MR 0754427
    .
  12. ^
    doi:10.1002/net.3230110211
  13. ISBN 9781420099829

External links
Retrieved from "https://en.wikipedia.org/w/index.php?title=Chinese_postman_problem&oldid=1205414764"