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~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.