### Abstract

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 ^{wmin} and ^{wmax}, and two real numbers ^{dmin} and ^{dmax}, a path P in a tree is feasible if the sum of the edge weights in P is between ^{wmin} and ^{wmax}, 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 ^{dmax}. In this paper, we first present an O(nlog^{2}n+h)-time algorithm to find all feasible paths in a tree, where h=O(^{n2}) if the output of a path is given by its end-nodes. Then, we present an O(nlog^{2}n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(nlog^{2}n+h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths.

Original language | English |
---|---|

Pages (from-to) | 126-134 |

Number of pages | 9 |

Journal | Discrete Applied Mathematics |

Volume | 180 |

DOIs | |

Publication status | Published - 2015 Jan 10 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Applied Mathematics

### Cite this

*Discrete Applied Mathematics*,

*180*, 126-134. https://doi.org/10.1016/j.dam.2014.07.024

}

*Discrete Applied Mathematics*, vol. 180, pp. 126-134. https://doi.org/10.1016/j.dam.2014.07.024

**Weight-constrained and density-constrained paths in a tree : Enumerating, counting, and k-maximum density paths.** / Lee, Chia Wei; Chen, Pin Liang; Hsieh, Sun Yuan.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Weight-constrained and density-constrained paths in a tree

T2 - Enumerating, counting, and k-maximum density paths

AU - Lee, Chia Wei

AU - Chen, Pin Liang

AU - Hsieh, Sun Yuan

PY - 2015/1/10

Y1 - 2015/1/10

N2 - 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 wmin and wmax, and two real numbers dmin and dmax, a path P in a tree is feasible if the sum of the edge weights in P is between wmin and wmax, 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 dmax. In this paper, we first present an O(nlog2n+h)-time algorithm to find all feasible paths in a tree, where h=O(n2) if the output of a path is given by its end-nodes. Then, we present an O(nlog2n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(nlog2n+h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths.

AB - 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 wmin and wmax, and two real numbers dmin and dmax, a path P in a tree is feasible if the sum of the edge weights in P is between wmin and wmax, 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 dmax. In this paper, we first present an O(nlog2n+h)-time algorithm to find all feasible paths in a tree, where h=O(n2) if the output of a path is given by its end-nodes. Then, we present an O(nlog2n)-time algorithm to count the number of all feasible paths in a tree. Finally, we present an O(nlog2n+h)-time algorithm to find the k feasible paths whose densities are the k largest of all feasible paths.

UR - http://www.scopus.com/inward/record.url?scp=84922214812&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84922214812&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2014.07.024

DO - 10.1016/j.dam.2014.07.024

M3 - Article

AN - SCOPUS:84922214812

VL - 180

SP - 126

EP - 134

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -