Problem Detail: I’m looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$
Output: the maximum-cost subtree containing $le k$ edges For purposes of this problem, a subtree is defined to be a connected subset of edges. Each edge of the tree has a cost, and the cost of a subtree is the sum of the costs of the edges in the subtree. Only edges have a cost, which is always positive. The tree always has a root node from which only one path originates and from which we must search, in the example it is the node numbered 1. I read somewhere that it’s possible to use a hashing function to compute it, but there was no explanation given. I would also be interested to learn of an algorithm that works for graphs that aren’t just binary trees. Here’s an example, with the desired subtree marked in yellow:
Output: the maximum-cost subtree containing $le k$ edges For purposes of this problem, a subtree is defined to be a connected subset of edges. Each edge of the tree has a cost, and the cost of a subtree is the sum of the costs of the edges in the subtree. Only edges have a cost, which is always positive. The tree always has a root node from which only one path originates and from which we must search, in the example it is the node numbered 1. I read somewhere that it’s possible to use a hashing function to compute it, but there was no explanation given. I would also be interested to learn of an algorithm that works for graphs that aren’t just binary trees. Here’s an example, with the desired subtree marked in yellow:
Asked By : Jakub Kawalec
Answered By : Raphael
Say our tree is $T = (V, E)$ with weight function $w : E to mathbb{Q}$ and $|V| = n$, and we are looking for the maximum-weight subtree with at most $k$ edges. There is a $Theta(nk^2)$-time and $Theta(nk)$-space algorithm for binary trees that uses ideas from dynamic programming. Idea: Store in every node $v$ the maximum weight obtainable using $i in 1, dots, k$ edges for a subtree rooted in $v$, as well as two pairs $(b_l, k_l)$ and $(b_r, k_r)$ for each $i$ that indicate if the left resp. right edges is chosen, and how many edges are chosen from each subtree; that is, $b_l + k_l + b_r + k_r = i$. Compute these numbers bottom-up; the leaves initialize with all zeroes. Details:
for v ∈ V { for i ∈ [1..k] { v.maxWeight[i] = 0 v.chooseLeft[i] = 0 v.edgesLeft[i] = 0 v.chooseRight[i] = 0 v.edgesRight[i] = 0 } } globalMax = [null, 0, -1] def annotate(v) { if v is not a leaf { annotate(v.left) annotate(v.right) for i ∈ [1..k] { for j ∈ [0..i] { w = [j > 0] * w((v, v.left)) + v.left.maxWeight[max(0,j-1)] + [i-j > 0] * w((v, v.right)) + v.right.maxWeight[max(0,i-j-1)] if w > v.maxWeight[i] { v.maxWeight[i] = w v.chooseLeft[i] = min(j,1) v.edgesLeft[i] = max(0,j-1) v.chooseRight[i] = min(i-j,1) v.edgesRight[i] = max(0,0-j-1) } } if v.maxWeight[i] > globalMax[2] { globalMax = [v, i, v.maxWeight[i]] } } } } annotate(T.root) What remains then is to move top-down from globalMax[0] and follow the chooseX[_] links with edgesX[_] to construct the optimal subtree with globalMax[1] edges and weight globalMax[2]. Proof of correctness (by induction) and analysis are elementary. The idea extends to trees of higher degree but then the factor $k^2$ changes to something more vicious; every node contributes something of the order of $k^{operatorname{deg}(v)}$ then, if implemented naively.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/59580 Ask a Question Download Related Notes/Documents
