Liu, Hsiao-FeiHsiao-FeiLiuKUN-MAO CHAO2018-09-102018-09-10200803043975https://www.scopus.com/inward/record.uri?eid=2-s2.0-53249153467&doi=10.1016%2fj.tcs.2008.06.052&partnerID=40&md5=16e5f3e024b9f088527ebc40f2bd7246http://scholars.lib.ntu.edu.tw/handle/123456789/339643In 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.application/pdf899446 bytesapplication/pdfMaximum-sum segment; Sequence analysisControl theory; Function evaluation; Computation tree; Lower bounds; Maximum-sum segment; New results; Paths problem; Positive integers; Sequence analysis; Weight functions; Trees (mathematics)journal article10.1016/j.tcs.2008.06.0522-s2.0-53249153467