# 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. – hugomg Apr 13 '12 at 21:39
• I know, but I am still curious to know how to do that. – Sim Apr 13 '12 at 21:48
• These lecture notes treat the Chinese Postman Problem: win.tue.nl/~nikhil/courses/2WO08/lec4.pdf – Alex ten Brink Apr 13 '12 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 '12 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 '12 at 17:17