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

DOI10.1016/J.DAM.2014.07.024MaRDI QIDQ476312zbMATH OpenOpenAlexFDO

Authors Chia-Wei Lee, Pin-Liang Chen, 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

treesnetwork designdesign and analysis of algorithms\(k\)-maximum density path problemcounting modefeasible paths

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Paths and cycles (05C38) Density (toughness, etc.) (05C42)

Recommendations

• Finding a length-constrained maximum-density path in a tree
• Algorithms and Computation
• Algorithms and Computation
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• An optimal algorithm for the maximum-density path in a tree

Cites work

• A Linear Time Algorithm for the k Maximal Sums Problem
• Algorithms and Computation
• An Optimal Algorithm for the Maximum-Density Segment Problem
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree
• An optimal algorithm for selection in a min-heap
• Dependence of densities on a parameter
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Finding a length-constrained maximum-density path in a tree
• Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
• Finding a longest nonnegative path in a constant degree tree
• Finding a maximum-density path in a tree under the weight and length constraints
• Introduction to algorithms.
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• Priority Search Trees
• Self-Adjusting Heaps
• Time bounds for selection

Cited in

(5)

• Algorithms and Computation
• Algorithms and Computation
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Finding a length-constrained maximum-density path in a tree
• An optimal algorithm for the maximum-density path in a tree

Describes a project that uses

Uses Software

• EMBOSS
• heapsort

This page was built for publication: Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476312)