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.


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)

| cite | improve this answer | |
  • $\begingroup$ I am interested in a similar decomposition. $\endgroup$ – h.a Jan 12 '11 at 5:44

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.