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 Ω(VlogV+k) in the algebraic computation tree model and give an O(VlogV+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.