<p>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?</p>

<p>In the former case, the following paper gives an $\mathcal{O}\big(n(m + \log n)\big)$ exact algorithm:<br>
<a href="http://portal.acm.org/citation.cfm?id=320176.320229" rel="nofollow">H.N.Gabow. Data Structures for Weighted Matching and Nearest Common Ancestors witk Linking. SODA'90 (1990)</a><br>
And for a $(2/3 - \epsilon)$-approximation algorithm running in $\mathcal{O}(m \log 1/\epsilon)$:<br>
<a href="http://dx.doi.org/10.1016/j.ipl.2004.05.007" rel="nofollow">S.Pettie, P.Sanders. A Simpler Linear $2/3 - \epsilon$ Approximation Algorithm for Maximum Weight Matching. Information Processing Letters, vol.91 (2004)</a></p>

CC BY-SA 2.5
2011-01-12T05:44:37.967Z
I am interested in a similar decomposition.
h.a
CC BY-SA 2.5
2011-01-11T13:48:54.427Z
2011-01-11T13:48:54.427Z
Mathieu Chapelle
<p>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:</p>

<p>M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting. <a href="http://dx.doi.org/10.1007/3-540-48481-7_38" rel="nofollow">A decomposition theorem
for maximum weight bipartite matchings with applications to evolutionary
trees</a>. In Proc. of the 7th Annual European Symposium on Algorithms (ESA’99),
pages 438–449, 1999.</p>

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

<p>Thank you.</p>

<graph-theory><co.combinatorics><matching>
A decomposition theorem for maximum weight matchings
h.a
# A decomposition theorem for maximum weight matchings

(Asked by: username_0 on 2011-01-10)

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](http://dx.doi.org/10.1007/3-540-48481-7_38). 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.

**Tags:** graph-theory, co.combinatorics, matching


---

## 1 answers

### Answer by username_1 on 2011-01-11. Score: 4

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)](http://portal.acm.org/citation.cfm?id=320176.320229)  
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)](http://dx.doi.org/10.1016/j.ipl.2004.05.007)

> **Comments:**
> **username_0**: I am interested in a similar decomposition.  

---

