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

研究成果: Article同行評審

摘要

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.

原文English
頁(從 - 到)126-134
頁數9
期刊Discrete Applied Mathematics
180
DOIs
出版狀態Published - 2015 一月 10

All Science Journal Classification (ASJC) codes

  • 離散數學和組合
  • 應用數學

指紋

深入研究「Weight-constrained and density-constrained paths in a tree: Enumerating, counting, and k-maximum density paths」主題。共同形成了獨特的指紋。

引用此