Linear-Time Algorithm for the Length-Constrained Heaviest Path Problem in a Tree with Uniform Edge Lengths
Given a tree T with edge lengths and edge weights, and a value B, the length-constrained heaviest path problem is to find a path in T with maximum path weight whose path length is at most B. We present a linear time algorithrn for the problem when the edge lengths are uniform, i.e., all one. This algorithm with slight modification can be used to find the heaviest path of length exactly B in T in linear time.
heaviest paths uniform edge lengths length-constrained paths