Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
From MaRDI portal
Publication:476312
DOI10.1016/j.dam.2014.07.024zbMath1303.05088MaRDI QIDQ476312
Pin-Liang Chen, Chia-Wei Lee, Sun-Yuan Hsieh
Publication date: 28 November 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.07.024
trees; network design; design and analysis of algorithms; \(k\)-maximum density path problem; counting mode; feasible paths
68W40: Analysis of algorithms
05C05: Trees
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
05C30: Enumeration in graph theory
05C38: Paths and cycles
05C85: Graph algorithms (graph-theoretic aspects)
05C42: Density (toughness, etc.)
Uses Software
Cites Work
- Unnamed Item
- An efficient algorithm for the length-constrained heaviest path problem on a tree
- Dependence of densities on a parameter
- Finding a longest nonnegative path in a constant degree tree
- Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
- An improved algorithm for finding a length-constrained maximum-density subtree in a tree
- Time bounds for selection
- Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
- Finding a length-constrained maximum-density path in a tree
- Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
- An optimal algorithm for selection in a min-heap
- Finding a maximum-density path in a tree under the weight and length constraints
- A Linear Time Algorithm for the k Maximal Sums Problem
- Priority Search Trees
- An Optimal Algorithm for the Maximum-Density Segment Problem
- Self-Adjusting Heaps
- Algorithms and Computation