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

摘要

Let T be a tree of n 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 W-min and W-max and two real numbers d(min) and d(max) a path P in a tree is feasible if the sum of the edge weights in P is between W-min and W-max and the ratio of the sum of the edge values in P to the sum of the edge weights in P is between dmin and dm. In this paper, we first present an O(n log(2) n+ h)time algorithm to find all feasible paths in a tree, where h = O(n(2)) if the output of a path is given by its end-nodes. Then, we present an O(n log(2) n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(n log(2) n + h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths. (C) 2014 Elsevier B.V. All rights reserved.