Question

2. (20pts) Let T (V, E) be a tree with positive weight on the edges. Its maximum matching is a set of edges in E with the maximum weight sum, each two of which share no common node. For example aiven T 2. 2. 8 3?

Answer 1

Notes about the pseudocode:

• The following algorithm uses dynamic programming to find the maximum matching.
• The algorithm Matching takes a tree T(V,E) as the parameter and returns the maximum matching for that Tree. The tree is passed in the form of the root node of the tree.
• Two global arrays are used to maintain the maximum-matching of a subtree rooted at the vertex V.

Algorithm Screenshots:

Pseudocode:

Algorithm Matching(T):

  Global Array inc_array[]

  Global Array exc_array[]

  if T has no child:

    exc_array[T] = 0

    inc_array[T] = 0

    return 0

if exc_array[T] is not computed:

    for V in T’s children:

        exc_array[V] = exc_array[V] + Matching(V)

if(inc_array[T] is not computed):

    max_match = 0

    curr_match = 0

    without_V= 0

    other_child = 0

   

    for V in T’s children:

        without_ V = without_ V + Matching(V)

   

      for V1 in T’s children and V1 is not V:

         other_child = other_child + Matching(V1)

   

      curr_match = weight(T,V) + without(V) + other_child

     

      if curr_match > max_match:

       max_match = curr_match

    inc_array[T] = max_match

   

return max (inc_array[T], exc_array[T])

Time Complexity:

• In the worst-case, the matching for none of the vertices of the tree is calculated.
• Let the number of vertices in the tree be V.
• The first for loop will recursively call the algorithm for all its children and a child will then recursively call for each of its child and so on. Therefore, all the vertices of the graph will be visited once.
• Hence, the first for loop makes V calls in the worst case.
• The second loop makes approximately V + V calls.
• Therefore, the total running time of the algorithm is O(V + V + V) = O(V)