ghost016's blog

Maximum Matching in the tree
By ghost016, 14 years ago, In English
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
  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
14 years ago, # |
  Vote: I like it +16 Vote: I do not like it
As far as I understand, your problem is: "You have a weighted tree, you need to find maximal matching".
You can do simple DP.
dp1[v] - The maximal matching of the subtree rooted by v where v is already covered by matching.
dp2[v] - The maximal matching of the subtree rooted by v where v isn't covered by matching yet.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Actually the algorithm described above finds exactly what you need, i.e. maximum matching.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        All right then. Well in that case can you please tell me what is the run-time of this algorithm ??

        Thanks
        Ghost016
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          If it is implemented optimally, then the complexity is O(N).
          → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    And i thought the best you could do is E*SQRT(V) using hopcroft!
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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.
      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply