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

\(k\)-maximum density path problemcounting modedesign and analysis of algorithmsfeasible pathsnetwork designtrees

Mathematics Subject Classification ID

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

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 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
• An Optimal Algorithm for the Maximum-Density Segment Problem
• 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)

• 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

Describes a project that uses

Uses Software

• heapsort
• EMBOSS

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)