An efficient algorithm for the length-constrained heaviest path problem on a tree
DOI10.1016/S0020-0190(98)00194-XzbMATH Open1339.68215OpenAlexW2070523096MaRDI QIDQ294615FDOQ294615
Chuan Yi Tang, Bang Ye Wu, Kun-Mao Chao
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
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)
Cites Work
- 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
- An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
- 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.
- Title not available (Why is that?)
- 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
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- On the \(K\) shortest path trees problem 👍 👎
- Approximation algorithms for the shortest total path length spanning tree problem 👍 👎
- Finding a length-constrained maximum-density path in a tree 👍 👎
- Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network 👍 👎
- 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 👍 👎
- 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 👍 👎
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)
