2
$\begingroup$

Suppose we have a weighted binary tree $G$ where the nodes are towns and edges are streets with edge weights being the travel time and we want to find out whether it is possible to travel from any town to any other town within some time $x$.

There are three paths to consider for each node $v$.

  1. Path to the right subtree of $v$
  2. Path to the left subtree of $v$
  3. Path that goes from the left to the right subtree including $v$

My approach to solving this problem is to use dynamic programming and start at leaf nodes to calculate a travel time $T_l$ for every leaf $l$ and set $T_l = 0$. Then work my way up the tree and compute $T_v = max(T_c + w(v,c))$ for every other node where $c$ are the child nodes of $v$ and check if that value is smaller than the given $x$. This would cover the first two cases and would require us to iterate over every node and edge once which is in $O(V+E)$

Where Im not sure is how to cover the third case, i.e. if I wanted to compute the travel time from one leaf node to another. Is that still possible in linear time and how would I do that?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Your dynamic program is a step in the right direction. My idea would be to maintain two values for a node v:

  1. $L_v$: The longest path starting from v going downwards (these corresponds to your dynamic program and the first two cases)
  2. $U_v$: and the longest path in the subtree of v (i.e., case 3).

You already gave the formula for $L_v$. For $U_v$ you take the maximum of $U_l$, $U_r$ and $L_l + w(lv) + w(rv) + L_r$ where $l$ and $r$ are the left and right children of v resp. The last equation corresponds to the path which is formed by the longest paths to the left and to the right which are then joined.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Daniel, I think that works. I'm wondering that if we don't have negative edge weights in the tree if we still need to consider $U_l$ and $U_r$. And I also wonder if it is still a linear time algorithm if we don't have a binary tree but an n-ary tree, i.e. nodes can have more than two children. $\endgroup$
    – Max
    Commented Sep 17, 2019 at 15:02
  • $\begingroup$ About non-negative edge weights: you'll need $U_v$ at least in the root because there the U path is longer than the L path. This can be extended such that it propagates from an inner node to a root. About k-ary children: Computing the L value won't take more time. For computing the U value the trivial way would be to check every pair of children, i.e. k² many combinations. But IMO it should suffice to consider only the two children with the highest L value and the child with the highest U value $\endgroup$
    – Daniel
    Commented Sep 19, 2019 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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