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.
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 ?
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?