An efficient algorithm for the length-constrained heaviest path problem on a tree

DOI10.1016/S0020-0190(98)00194-XMaRDI QIDQ294615zbMATH OpenOpenAlexFDO

Authors Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang

Publication date 16 June 2016

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

Full work available at URL http://www.sciencedirect.com/science/article/pii/S002001909800194X?np=y

zbMATH Keywords

treesnetwork designheaviest path problem

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees
• An optimal algorithm for the maximum-density path in a tree
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network
• scientific article; zbMATH DE number 2080243
• Finding a length-constrained maximum-density path in a tree
• Algorithms and Computation
• scientific article; zbMATH DE number 1094324
• On the \(K\) shortest path trees problem
• Approximation algorithms for the shortest total path length spanning tree problem

Cites work

• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
• Efficient Algorithms for Finding a Core of a Tree with a Specified Length

Cited in

(15)

• Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• scientific article; zbMATH DE number 2080243 (Why is no real title available?)
• Finding a maximum-density path in a tree under the weight and length constraints
• The heaviest induced ancestors problem: better data structures and applications
• A pathfinding problem for search trees with unknown edge length
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees
• An optimal algorithm for the maximum-density path in a tree
• Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths
• Finding a length-constrained maximum-density path in a tree
• Finding a longest nonnegative path in a constant degree tree
• An improved algorithm for finding a length-constrained maximum-density subtree in a tree
• Algorithms and Computation
• The density maximization problem in graphs

This page was built for publication: An efficient algorithm for the length-constrained heaviest path problem on a tree

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