We are given a rooted, directed tree T (not necessarily binary), with n nodes. E

Question

We are given a rooted, directed tree T (not necessarily binary), with n nodes. Each leaf of T is labeled by a single single character. The same character can label several different leaves. We want to label each interior node of the tree with a single character so as to minimize the number of edges whose endpoints have different labels. This problem can be solved with dynamic programming. For any node v, let T_v be the subtree of T rooted at node v. That is, T_v consists of node v and all the nodes below v in T. Let C(v) be the cost of the optimal solution to the problem when restricted to subtree T_v alone. For every character x, let C( v,x) be the cost of the best labeling of subtree T_v when node v is lrequired to be labeled with character x. And let v, denote the i'th child of node v. The base cases for the DP specify the values of C(v) and C(v,x), for every leaf v of T, and every character x in the alphabet. Specifically, for each leaf v, C(v) = 0, and C(v,x) = 0 if x is the input character that labels leaf v, and C(v,x) = infinity if x is not the input character that labels v. When r is an internal node, then

Explanation / Answer

a) This relation is correct mainly beacuse of the two properties of Dynamic programming:

i ) Breaking down into subproblems

ii) Choosing the most Optimal one

b) We can still make the same recurrence call but saving the values in a matrix:

C[ v ][x] denotes that vertex v is given color x

c) O(n)

d) Similar to the way the recurrence was called, check which is the most minimum one and assign character to it.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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