Algorithms for finding the weight-constrained k longest paths in a tree and the length-constrained k maximum-sum segments of a sequence

In this work, we obtain the following new results: -Given a tree T = (V, E) with a length function ℓ : E → R and a weight function w : E → R, a positive integer k, and an interval [L, U], the Weight-ConstrainedkLongest Paths problem is to find the k longest paths among all paths in T with weights in the interval [L, U]. We show that the Weight-ConstrainedkLongest Paths problem has a lower bound Ω (V log V + k) in the algebraic computation tree model and give an O (V log V + k)-time algorithm for it.-Given a sequence A = (a1, a2, ..., an) of numbers and an interval [L, U], we define the sum and length of a segment A [i, j] to be ai + ai + 1 + ⋯ + aj and j - i + 1, respectively. The Length-ConstrainedkMaximum-Sum Segments problem is to find the k maximum-sum segments among all segments of A with lengths in the interval [L, U]. We show that the Length-ConstrainedkMaximum-Sum Segments problem can be solved in O (n + k) time. © 2008 Elsevier B.V. All rights reserved.