Weight-constrained and density-constrained paths in a tree: Enumerating, counting, and kk-maximum density paths

Let TT be a tree of nn nodes in which each edge is associated with a value and a weight that are a real number and a positive integer, respectively. Given two integers wminwmin and wmaxwmax, and two real numbers dmindmin and dmaxdmax, a path PP in a tree is feasible   if the sum of the edge weights in PP is between wminwmin and wmaxwmax, and the ratio of the sum of the edge values in PP to the sum of the edge weights in PP is between dmindmin and dmaxdmax. In this paper, we first present an O(nlog2n+h)O(nlog2n+h)-time algorithm to find all feasible paths in a tree, where h=O(n2)h=O(n2) if the output of a path is given by its end-nodes. Then, we present an O(nlog2n)O(nlog2n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(nlog2n+h)O(nlog2n+h)-time algorithm to find the kk feasible paths whose densities are the kk largest of all feasible paths.