Chinese Postman problem

From Algorithmist
Jump to: navigation, search

Definition[edit]

Given a directed or undirected graph. You are to find a minimum length closed walk that traverses each edge at least once.

Algorithms[edit]

Chinese Postman problem (CPM) in directed graphs can be solved by computing minimum-cost matching in a bipartite graph. One partition contains vertices for which in-degree exceeds out-degree (additionally, each such vertex occurs in-degree - out-degree times), similarly the other partition contains vertices for which out-degree exceeds in-degree. Weight of each edge is equal to length of shortest directed path in the original graph from the vertex of the first partition to the vertex in the second partition. After finding the matching, add to the graph shortest paths corresponding to edges in the matching, and find Euler tour.

In undirected graphs CPM can be solved by finding minimum-cost matching in a general (not necessarily bipartite) graph, containing the odd-degree vertices of the original graph. Weight of each edge is equal to length of shortest path in the original graph between the edge's vertices.

In mixed graph (containing both directed and undirected edges at the same time), CPM is NP-complete.

See also[edit]