Page 1 of 1
Let T = (V, E) be a tree with positive edge weights w(e). Recall that a matching M is a subset of edges such that no two
Posted: Fri Jun 10, 2022 11:54 am
by correctanswer
- Let T V E Be A Tree With Positive Edge Weights W E Recall That A Matching M Is A Subset Of Edges Such That No Two 1 (284.87 KiB) Viewed 115 times
Let T = (V, E) be a tree with positive edge weights w(e). Recall that a matching M is a subset of edges such that no two edges in M are incident on the same vertex. The maximum weight matching problem is to find a matching M maximizing the sum of the weights of the edges in M, that is, maximize Σeɛm w(e). Your task is to design a dynamic programming algorithm that computes the weight of the maximum weight matching. (Note that your algorithm does not need to output the actual maximum weight matching, just its weight.) For full marks your algorithm should run in O(n) time where n is the number of vertices in T. (a) Clearly define the DP subproblems. (b) State and justify the recurrence and base cases. (c) Analyze its time complexity.