9
$\begingroup$

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)

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ Wikipedia sais that there is an $O(n^3)$ algorithm for the Chinese Postman Problem. $\endgroup$ – hugomg Apr 13 '12 at 21:39
  • $\begingroup$ I know, but I am still curious to know how to do that. $\endgroup$ – Sim Apr 13 '12 at 21:48
  • 2
    $\begingroup$ These lecture notes treat the Chinese Postman Problem: win.tue.nl/~nikhil/courses/2WO08/lec4.pdf $\endgroup$ – Alex ten Brink Apr 13 '12 at 23:59
  • $\begingroup$ 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 $\endgroup$ – user1799 Jun 8 '12 at 17:12
  • $\begingroup$ 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. $\endgroup$ – Sim Jun 10 '12 at 17:17
1
$\begingroup$

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++ [1].

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ And let's not call it the "Chinese Postman Problem". The only link to China is that it was introduced by Mei-Ko Kwan and his nationality is irrelevant to the problem. Naming it "Chinese" suggests that the most significant thing about him is his ethnic origin. We don't, for example, refer to the well-known algorithm for computing shortest paths in graphs as "the Dutch algorithm" or, even worse, "the white man's algorithm". (Yes, I object to "Chinese remainder theorem" for the same reason but that horse bolted too long ago.) $\endgroup$ – David Richerby Jan 2 '14 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.