Abstract
Given a tree with weight and length on each edge, this paper presents an efficient algorithm for locating the length-constrained heaviest path on the tree. The time complexity of the algorithm is O(n log 2 n) and can be reduced to O(n log n) if the edge lengths are all integers in the range 1 to O(n), where n is the number of vertices. It is also shown that several similar problems can be solved by the same algorithm. © 1999 Published by Elsevier Science B.V. All rights reserved.