Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
DOI10.1016/j.dam.2014.07.024zbMath1303.05088OpenAlexW2014621601MaRDI 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
treesnetwork designdesign and analysis of algorithms\(k\)-maximum density path problemcounting modefeasible paths
Analysis of algorithms (68W40) Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)
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
This page was built for publication: Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
