Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths

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

zbMATH Keywords

trees; network design; design and analysis of algorithms; \(k\)-maximum density path problem; counting mode; feasible paths

Mathematics Subject Classification ID

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

• EMBOSS
• heapsort

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