A decomposition theorem for maximum weight matchings

Question

The following paper presents a way to solve the maximum weight matching of a bipartite graph by reducing it to computing maximum weight matchings of two lighter bipartite graphs:

M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Proc. of the 7th Annual European Symposium on Algorithms (ESA’99), pages 438–449, 1999.

Is there a generalization of the result which also holds for non-bipartite weighted graphs?

Thank you.

Answer 1

Are you actually looking for a polynomial time algorithm solving maximum weight matching for general graphs, or a specific way to solve it using a kind of decomposition?

In the former case, the following paper gives an $\mathcal{O}\big(n(m + \log n)\big)$ exact algorithm:
H.N.Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors witk Linking. SODA'90 (1990)
And for a $(2/3 - \epsilon)$-approximation algorithm running in $\mathcal{O}(m \log 1/\epsilon)$:
S.Pettie, P.Sanders. A Simpler Linear $2/3 - \epsilon$ Approximation Algorithm for Maximum Weight Matching. Information Processing Letters, vol.91 (2004)