An efficient algorithm for the length-constrained heaviest path problem on a tree

[[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 log2 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.[[fileno]]2030209010018[[department]]資訊工程學