An efficient algorithm for the length-constrained heaviest path problem on a tree
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. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
algorithms trees network design divide and conquer