# Chinese Postman Problem: finding best connections between odd-degree nodes

I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to connect the nodes with odd degree, so I can compute an Eulerian circuit.

There might be (considering the size of the graph that wants to be solved) an enormous combination of edges which need to be computed and evaluated.

As an example there are the odd-degree nodes $A, B, C, D, E, F, G, H$. The best combinations could be:

1. $AB$, $CD$, $EF$, $GH$
2. $AC$, $BD$, $EH$, $FG$
3. $AD$, $BC$, $EG$, $FH$
4. $AE$ ....

where $AB$ means "edge between node $A$ and node $B$".

Therefore my question is: is there a known algorithm to solve that problem in a complexity better than pure brute force (computing and evaluating them all)?

€:After some research effort I found this article, speaking about the "Edmonds' minimum-length matching algorithm" but I cannot find any pseudo-code or learners-descriptions of this algorithm (or at least I do not recognize them, as Google offers a lot of hits an matching algorithms by J. Edmonds)

• Wikipedia sais that there is an $O(n^3)$ algorithm for the Chinese Postman Problem. Apr 13, 2012 at 21:39
• I know, but I am still curious to know how to do that.
– Sim
Apr 13, 2012 at 21:48
• These lecture notes treat the Chinese Postman Problem: win.tue.nl/~nikhil/courses/2WO08/lec4.pdf Apr 13, 2012 at 23:59
• Sim, I am interested in your software since I am facing a mapping problem: help.openstreetmap.org/questions/13197/… Good luck with your project. pm at pmbooks dot com
– user1799
Jun 8, 2012 at 17:12
• try the article I linked it describes a minimum length matching algorithm, but due to my lack of experience and the lack of pseudo-code I sadly was not able to implement it.
– Sim
Jun 10, 2012 at 17:17