The Chinese Postman problem (A.K.A Route Inspection Problem)

I'm trying to match pairs of odd-degree nodes in a grid-graph representing an indoor map to ensure the graph is Eulerian (consists only of nodes with even degrees). My plan is to form a matching between the odd-degree nodes and consider Euler paths of the graph augmented by this matching. Matchings of different weights will lead to augmented graphs whose Euler paths have different lengths.

  1. Obviously, if the number of nodes is large, the complexity of matching using brute-force grows in a non-polynomial manner. Hence, I first thought about grouping closest (based on Euclidean distance NOT shortest-path) pairs together using the recursive divide and conquer approach resulting in a time complexity of $O(n\log n)$. I understand that this would not result in a graph with the optimal Euler path. Do you think there are other problems other than the optimality of the generated Euler Circuit ?

  2. I understand that Edmonds' matching algorithm guarantees an optimal pairing of odd nodes. However, I can't find a decent source that describes the algorithm in a simple manner. Could you kindly provide me with any source other than Edmonds' paper?

  • $\begingroup$ My aim is to find an Euler path when you have odd vertices. If you have odd vertices, you have to create artificial edges between the odd nodes (matching problem) to be able convert the graph into a graph with even vertices. Then you can find an Euler path. It is true that all Eulerian paths are of the same length. But if the matching between the odd nodes is not optimal, the resulting tour will not be optimal. $\endgroup$ – Anas Mahmoud Apr 21 '17 at 16:14
  • $\begingroup$ I see now. I edited your question to make that clearer -- please check that I didn't make a mess of it! Do feel free to edit if you don't like my version. $\endgroup$ – David Richerby Apr 21 '17 at 17:04
  • $\begingroup$ I think its clearer now. Thanks DavidRicherby $\endgroup$ – Anas Mahmoud Apr 21 '17 at 20:11
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/74283/755, math.stackexchange.com/q/2244454/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Apr 24 '17 at 20:51
  • $\begingroup$ We prefer that you ask only one question per post. Also, we prefer focused questions rather than open-ended questions. "Do you think there are other problems...?" is too open-ended, because we're forced to guess what you might consider to be a problem. Instead, it might be better to identify what are the requirements and then ask something about that (e.g., "does algorithm X have property Y?", "does algorithm X meet requirement Z?"). $\endgroup$ – D.W. Apr 24 '17 at 20:54

Your Answer

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

Browse other questions tagged or ask your own question.