Algorithms and Complexity – DP Max Weight Matching in Tree [latex][/latex]

Given:
Tree $T$ , $w:E\Rightarrow \mathbb{R}$
Want:
Give poly-time algorithm for finding max weight matching
Solve:
$A[u]=$ cost of max weight matching for sub-tree rooted at root.
Base case:

$A[u]=0$ when $u$ is a leaf node
for internal node:

case 1: $u$ is unmatched
case 2: $u$ is matched to one of its children

First, look at a sub-tree from $root$ , $u$

Rendered by QuickLaTeX.com

Case 1: when $u$ is not matched $\rightarrow A[u]=\sum_{v\text{ child of u}}A[v]$ , this means its children must all match to some of their children. Look at the thick edges.

Rendered by QuickLaTeX.com

Case 2: when $u$ is matched to $v$ so

$A[u]=max\{\text{case 1}+\text{case 2}+\text{case 3}\}$

$A[u]=max\{w(u,v)+\sum_{x\text{ child of }u\text{ when }x \neq v} A[x]+\sum_{w\text{ child of }v}A[w]\}$

Rendered by QuickLaTeX.com

Sum up: answer is at $A[root]$ .
$A[u] = max \left\{ \begin{array}{cc} \sum\limits_{v\text{ child of }u}A[v]\\ \\ max\{w(u,v)+\sum\limits_{x\text{ child of }u\text{ when }x \neq v} A[x]+\sum\limits_{w\text{ child of }v}A[w]\} \end{array} \right.$

Running time:
$A[u] = max \left\{ \begin{array}{cc} O(degree(u))\\ O(c^2) \end{array} \right.$
where $O(degree(u))$ means how many children a certain node has.
Number of states: $n$
each state take $O(degree(u))$ .
so:
$\sum\limits_{u \in v}degree(u)=2m=2(n-1)=2n-2=O(n)$

Algorithms and Complexity – DP Max Weight Matching in Tree

One Comment

Leave a Comment

Recent Posts