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)