An improved algorithm for finding a length-constrained maximum-density subtree in a tree

DOI10.1016/j.ipl.2008.09.027zbMath1190.90257OpenAlexW2157026797MaRDI QIDQ975556

Chin Lung Lu, Hsin-Hao Su, Chuan Yi Tang

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.09.027

zbMATH Keywords

algorithmsdynamic programmingtreesnetwork designdivide and conquer

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (2)

Attack and defense in the layered cyber-security model and their \((1 \pm \varepsilon)\)-approximation schemes ⋮ Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths

Cites Work

• Unnamed Item
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
• Linear-time algorithm for finding a maximum-density segment of a sequence
• 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.
• Finding a maximum-density path in a tree under the weight and length constraints
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Algorithms and Computation

This page was built for publication: An improved algorithm for finding a length-constrained maximum-density subtree in a tree