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:


$AB$, $CD$, $EF$, $GH$
$AC$, $BD$, $EH$, $FG$
$AD$, $BC$, $EG$, $FH$
$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)
As remarked in the comments, Wikipedia gives a reduction from route inspection to minimum-weight matchings.  Vladimir Kolmogorov has published a fast implementation of the weighted version of Edmonds' blossom algorithm, in C++&nbsp;[1].

[1] V. Kolmogorov, Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43&ndash;67, 2009.