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

Chia Wei Lee, Pin Liang Chen, Sun Yuan Hsieh

Research output: Contribution to journalArticle

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(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.

Original languageEnglish
Pages (from-to)126-134
Number of pages9
JournalDiscrete Applied Mathematics
Volume180
DOIs
Publication statusPublished - 2015 Jan 10

Fingerprint

Counting
Path
Integer
Vertex of a graph
Count
Output

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this

@article{19cc7b94c9c0496e81a830bb33d9829a,
title = "Weight-constrained and density-constrained paths in a tree: Enumerating, counting, and k-maximum density paths",
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(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.",
author = "Lee, {Chia Wei} and Chen, {Pin Liang} and Hsieh, {Sun Yuan}",
year = "2015",
month = "1",
day = "10",
doi = "10.1016/j.dam.2014.07.024",
language = "English",
volume = "180",
pages = "126--134",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

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.

In: Discrete Applied Mathematics, Vol. 180, 10.01.2015, p. 126-134.

Research output: Contribution to journalArticle

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 -