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

Maximum Matching in the tree
Автор ghost016, 14 лет назад, По-английски
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
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +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.
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.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Actually the algorithm described above finds exactly what you need, i.e. maximum matching.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        All right then. Well in that case can you please tell me what is the run-time of this algorithm ??

        Thanks
        Ghost016
        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    And i thought the best you could do is E*SQRT(V) using hopcroft!
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить