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

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

dp_{1}[v] - The maximal matching of the subtree rooted by v where v is already covered by matching.dp_{2}[v] - The maximal matching of the subtree rooted by v where v isn't covered by matching yet.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

Thanks

Ghost016

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.This thing is really new for me and the theory really look nice .... can anyone please give me source code for this .... i am really interested to learn this ...

Thank You

Ghost016

Are there any problems in the Online Judges about Maximum Matching on the tree?

I cannot find (only there is minimum Vertex Cover on the tree).

I want to give it for my school students

In bipartite Graphs ( like trees ) maximum matching = vertex cover !

Hmmmmm. Mb it's http://acm.timus.ru/problem.aspx?space=1&num=1109 ?