To by understanding, the Micali-Vazirani algorithm (1980) is significantly better in time complexity than the blossom algorithm (1961) (Micali-Vazirani is O(V^{1/2} E) and blossom is O(V^2 E) for maximum cardinality matching in general graphs. Yet, the blossom seems to be much more widely used, even recently (1). Even packages desinged to solve these problems implement blossom over Micali-Vazirani (1). Why is this?
1 Answers
Micali-Vazirani does not support weights, the routine you linked from networkx is for finding a maximum weight matching. If your graph is bipartite and you don't need weights, people also resort to the much simpler Hopcroft-Karp which matches Micali-Vazirani's bound, also hampering its popularity. It's the complexity of implementing Micali-Vazirani that is the main hurdle, I believe.
The fully unconditional state of the art for maximum weight matching is not that much better than Edmonds O(mn2), there is the 1990 algorithm from Data structures for weighted matching and nearest common ancestors with linking by HN Gabow that solves it in O(mn + n2 log n). But at this small of a speedup the simplicity of the implementation of the algorithm and constant factors rule.
If you are okay with approximations there is an interesting complexity found in the 2014 paper Linear-Time Approximation for Maximum Weight Matching by Ran Duan and Seth Pettie (also containing a nice survey of algorithms), which can solve the problem in O(m/ɛ log(1/ɛ)) time for an (1-ɛ)-approximation. That is, if you are okay with the weight of your matching being, say, 10% off the maximum weight matching you get O(m) complexity.
Related