Maximum Matching in the tree

Блог пользователя ghost016

Автор ghost016, 13 лет назад, По-английски

Hello all,

Recently i am stuck with a problem, which i was trying on my own for couple of days, i have two different trees which are weighted, weights are assigned in some basis which are not of the concern now, anywayz i thought of transforming it into bipartite graph and then find the maximum weighted matching between them, but next i thought of doing the maximum tree matching rather then transforming into graph and then doing the match, now i am stuck here, i really want to know how to do it. Many good coders are here, please any one help me with this.

ThankS
Ghost016

match, maximum, tree

ghost016
13 лет назад
16

Комментарии (12)

Показать архивные | Написать комментарий?

niyaznigmatul

13 лет назад, # |

+16

As far as I understand, your problem is: "You have a weighted tree, you need to find maximal matching".

You can do simple DP.

dp₁[v] - The maximal matching of the subtree rooted by v where v is already covered by matching.

dp₂[v] - The maximal matching of the subtree rooted by v where v isn't covered by matching yet.

$\text{[math]}$

→ Ответить

ghost016

13 лет назад, # ^ |

Hello,
Thankz for your reply, however i asked for the maximum matching, not maximal matching, but thanks anywayz for the reply, and one more thing, can you please tell me an algorithm for these i.e for maximum matching which is btw faster then hungarian. And i am really bad at DP, i think this wont work with me, but i can see u formulated it nicely. Do you have a source code for this ???

Thanks
Ghost016

→ Ответить

KADR	13 лет назад, # ^ \| 0 Actually the algorithm described above finds exactly what you need, i.e. maximum matching. → Ответить

ghost016

13 лет назад, # ^ |

All right then. Well in that case can you please tell me what is the run-time of this algorithm ??

Thanks
Ghost016

→ Ответить

KADR	13 лет назад, # ^ \| 0 If it is implemented optimally, then the complexity is O(N). → Ответить

ksb	13 лет назад, # ^ \| 0 And i thought the best you could do is E*SQRT(V) using hopcroft! → Ответить

niyaznigmatul

13 лет назад, # ^ |

The problem is to find matching in tree, so we can use dynamic programming. Hopcroft-Karp algorithm is for cyclic bipartite graphs, although it can't find weighted matching. To find maximal matching in tree is quite easier than in cyclic graph.

→ Ответить