a) Suppose v is a leaf: What is the value of opt v (in), opt v, (out 1 ), opt v
ID: 3574861 • Letter: A
Question
a) Suppose v is a leaf:
What is the value of optv (in), optv, (out1), optv (out0)
b) Suppose v is an internal node (so v has exactly two children).
Give a recurrence for optv (in), (out1), optv (out0)
c) Give a linear-time algorithm to find a minimum-weight dominating set in a rooted full binary tree.
In this problem, you are asked to to design a linear-time algorithm to find a minimum-weight dominating set for the special case where the input graph is a rooted full binary tree T E i.e., T is a rooted tree where every node has 0 or 2 children. We use the following terminology. Let U be a subset of V and let v be any node in T. We say that v is dominated by U if either v EU or v is a neighbor of some node in U Let v be a vertex of T, let w be the weight of v, and let Tv denote the subtree of T rooted at v (obviously, T is itself a rooted full binary tree). For each s E n, outi, outol, define opt (s) as follows. opt (in) equals the minimum weight of a dominating set for Tv that includes at v. optu(outi) equals the minimum weight of an dominating set for T. that does not include v optu(outo) equals the minimum weight of a subset U of the nodes of T such that v is not dominated by U (so v U), but every other node of TV is dominated by UExplanation / Answer
c)MINIMUM WEIGHT DOMINATING SET
The MINIMUM WEIGHT DOMINATING SETS are equal to the maximal independent sets so the same algorithm works:
The Algorithm is as follows :
You can compute the maximum independent set by a depth first search through the tree.
The search will compute two values for each subtree in the graph:
These can be computed recursively by considering two cases:
The root of the subtree is not included.
B(i) = sum(max(A(j),B(j)) for j in children(i))
The root of the subtree is included.
A(i) = 1 + sum(B(j) for j in children(i))
The size of the maximum independent set in the whole tree is max(A(root),B(root)).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.