(35pts) Let T = (V,E) be a tree with positive weight on the edges. Its maximum m

Question

(35pts) 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 2. 2. 2 2. hot a maXimaim mal 2. 2. Cause A B ar shate d by multsple edjs Problem definition: Maximum Matching on a Tree Input: a tree (T, E) with the positive edge weight E Output: a maximum matching of T Design an 0(IVI) time algorithm to compute the problem. Write all of o your basic method in 3-10 lines, o complete pseudo code, o proof of the algorithm correctness, and o that of the running time Make your answers succinct but include everything necessary to reason the above. Hint: The simplest way uses dynamic programming. Note any node in T can be a root. Design your size parameter and recursion.

Explanation / Answer

package refactor.helper; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Hopcroft { private final int NIL = 0; private final int INF = Integer.MAX_VALUE; private ArrayList[] Adj; private int[] Pair; private int[] Dist; private int cx, cy; public boolean BFS() { Queue queue = new LinkedList(); for (int v = 1; v

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.