An optimal algorithm for the maximum-density path in a tree

DOI10.1016/j.ipl.2009.05.005zbMath1202.68477OpenAlexW2059509874MaRDI QIDQ989545

Bang Ye Wu

Publication date: 20 August 2010

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

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

zbMATH Keywords

treealgorithmsoptimization problemspine decomposition

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Mathematical programming (90C99)

Related Items

The density maximization problem in graphs

Cites Work

• 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
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• 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 \(O(pn^ 2)\) algorithm for the \(p\)-median and related problems on tree graphs
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Efficient computation of 2-medians in a tree network with positive/negative weights