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

DOI10.1016/J.IPL.2009.05.005MaRDI QIDQ989545zbMATH OpenOpenAlexFDO

Authors 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

algorithmsoptimization problemspine decompositiontree

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• Finding a length-constrained maximum-density path in a tree
• Algorithms and Computation
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths

Cites work

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

Cited in

(9)

• Finding a length-constrained maximum-density path in a tree
• A pathfinding problem for search trees with unknown edge length
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• The density maximization problem in graphs
• scientific article; zbMATH DE number 1093953 (Why is no real title available?)
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
• Algorithms and Computation
• scientific article; zbMATH DE number 2188361 (Why is no real title available?)
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree

This page was built for publication: An optimal algorithm for the maximum-density path in a tree

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