1
$\begingroup$

I have undirected weighted linear tree (path tree) with $n$ nodes ,and a weight function on edges $\omega: \mathbb{N}\to \mathbb{N}$, additionally given $k\in \mathbb{N}$, How we can find a path with lenght $k$ that have minimum number of edges in $O(n)$?enter image
description here

I think as follow: Run Bellman Ford for each node and then select a path with length $k$ and minimum number of edges. Unfortunately runtime $\omega(n)$.

$\endgroup$

1 Answer 1

1
$\begingroup$

The idea is to find, for each vertex $i$, the first vertex $j_i > i$ such that the distance $d(i, j_i)$ between $i$ and $j_i$ is at least $k$. Then, you can return the pair $(i, j_i)$ such that $d(i,j_i)=k$ and $j_i-i$ is minimized.

This takes $O(n)$ time once you notice that, for $i_1 < i_2$, $j_{i_1} \le j_{i_2}$. In pseudocode, where $w(\ell, \ell+1)$ denotes the weight of edge $(\ell, \ell+1)$:

i = j = 1
best_i = 0
best_j = n
d = 0

while i != n:
  if d<k and j!=n:
    d = d + w(j, j+1)
    j=j+1
  else:
    d = d - w(i, i+1)
    i=i+1

  if d == k and j - i < best_j - best_i:
    best_i=i
    best_j=j

return best_i, best_j
$\endgroup$
7
  • $\begingroup$ $j_i-i$ must maximized? i think must minimized. $\endgroup$
    – user133520
    Mar 24, 2021 at 21:39
  • $\begingroup$ @myarge. My bad. I fixed it. It doesn't make much of a difference anyway. $\endgroup$
    – Steven
    Mar 24, 2021 at 21:41
  • $\begingroup$ Hello, could you explain you idea in simple manner? Thank you. $\endgroup$
    – ErroR
    Apr 27, 2022 at 22:35
  • $\begingroup$ Scan the vertices of the path from left to right. For each vertex $i$, find the right endpoint as the leftmost vertex $j$ that is "to the right" of $i$ has is at a distance of at least $k$. The solution can be found by examining only these pairs $(i,j)$. To get a running time of $O(n)$ you can notice that the position of the vertices $j$ must either stay the same or move right, when $i$ changes. $\endgroup$
    – Steven
    Apr 28, 2022 at 8:02
  • $\begingroup$ Thank you. If the our tree has at most degree 3 for each vertex, can we solve the problem in $O(n^2\log n)$? $\endgroup$
    – ErroR
    Apr 28, 2022 at 8:26

Your Answer

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