Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm practicing solving algorithm problems and can't manage with this problem:

We are given a tree with $n$ vertices by the list of $n-1$ tuples: $\langle a_i, b_i, w_i\rangle$, where $a_i\neq b_i, \ 1\le a_i, b_i \le n, \ 1\le w_i\le 1000, \ 2\le n\le 300000$, which means that vertex with number $a_i$ is connected with $b_i$ and this edge has weight $w_i$. The problem is to find maximum weight-matching in this tree.

For example tree:

n = 7

1 - 3; 2 (which means that vertices 1,2 are connected with an edge with weight $2$)

3 - 2; 1

2 - 4; 5

2 - 5; 7

3 - 6; 10

6 - 7; 1

The answer is $17$ (we take edges with weights: $10$ and $7$).

I have heard that this problem is in general very difficult, but I suspect that the fact that the graph we are given is a tree, is a great convenience. But still don't know how to use it.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You can use dynamic programming to find an efficient ($O(n)$) solution for a tree. The standard matching algorithms (finding a maximum weight matching is not that hard) will give solutions too, even if they're less efficient.

share|improve this answer
    
Right! Easier than I thought. Thank you very much. –  xan Mar 4 '13 at 16:45

Hint:

Consider a rooted tree and let $\mathcal{T}$ be the set of all its subtrees. Let

  • $f : \mathcal{T} \to \mathbb{R}$ be a function that for a given tree $T$ returns the cost of any maximum-weight matching in $T$,
  • $g : \mathcal{T} \to \mathbb{R}$ be a function that for a givent tree $T$ returns the cost of maximum-weight matching in $T$ that does not use the root.

Then

\begin{align} g(T) &= \sum_{C \text{ child of } T} f(C), \\ f(T) &= g(T) + \max\left(0,\quad \max_{C \text{ child of } T} w_{\mathrm{root},C} + g(C) - f(C) \right). \end{align}

Good luck!

share|improve this answer
    
Thank you very much :-) –  xan Mar 4 '13 at 16:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.