We study the problem of finding a length-constrained maximum-density path in a tree with weight and length on each edge. This problem was proposed in [R.R. Lin, W.H. Kuo, K.M. Chao, Finding a length-constrained maximum-density path in a tree, Journal of Combinatorial Optimization 9 (2005) 147-156] and solved in O(nU) time when the edge lengths are positive integers, where n is the number of nodes in the tree and U is the length upper bound of the path. We present an algorithm that runs in O(nlog^2n) time for the generalized case when the edge lengths are positive real numbers, which indicates an improvement when U=@W(log^2n). The complexity is reduced to O(nlogn) when edge lengths are uniform. In addition, we study the generalized problems of finding a length-constrained maximum-sum or maximum-density subtree in a given tree or graph, providing algorithmic and complexity results.
['Hoong Chuin Lau', 'Trung Hieu Ngo', 'Bao Nguyen Nguyen']
Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics