3
$\begingroup$

I've got a weighted tree graph, where all the weights are positive. I need an algorithm to solve the following problem.

How many pairs of vertices are there in this graph, for which the sum of the weights of edges between them equals $C$?

I thought of a solutions thats $O(n^2)$

For each vertex we start a DFS from it and stop it when the sum gets bigger than $C$. Since the number of edges is $n-1$, that gives us obviously an $O(n^2)$ solution.

But can we do better asymptotics-wise?

$\endgroup$
4
$\begingroup$

If the weights are integers and $C$ is small relative to $n$, you may prefer an $O(nC)$ algorithm:

Select a root node, and process the vertices in postorder, For each vertex compute an array of how many vertices below it have distances $0, 1, 2, \ldots, C$ from it. Two such arrays can be combined to one in $O(C)$, time, while also counting how many paths of total weight $C$ span the particular two subtrees they describe.

$\endgroup$
  • $\begingroup$ Could you modify this technique for when the graph was not a tree, i.e. just some weighted directed graph, which may even contain cycles? $\endgroup$ – Mahatma Gandhi Jan 27 '17 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.