An efficient algorithm for the length-constrained heaviest path problem on a tree
From MaRDI portal
Publication:294615
DOI10.1016/S0020-0190(98)00194-XzbMath1339.68215OpenAlexW2070523096MaRDI QIDQ294615
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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. ⋮ Finding a longest nonnegative path in a constant degree tree ⋮ Finding a maximum-density path in a tree under the weight and length constraints ⋮ Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics ⋮ The density maximization problem in graphs ⋮ Weight-constrained and density-constrained paths in a tree: enumerating, counting, and \(k\)-maximum density paths ⋮ 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 improved algorithm for finding a length-constrained maximum-density subtree in a tree ⋮ Finding a length-constrained maximum-density path in a tree ⋮ An optimal algorithm for the maximum-density path in a tree
Cites Work
- An \(O(n)\) algorithm for finding an optimal position with relative distances in an evolutionary tree
- An Algorithmic Approach to Network Location Problems. I: Thep-Centers
- 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
This page was built for publication: An efficient algorithm for the length-constrained heaviest path problem on a tree
