Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence

DOI10.1016/j.tcs.2008.06.052zbMath1151.90057MaRDI QIDQ955012

Kun-Mao Chao, Hsiao-Fei Liu

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.06.052

zbMATH Keywords

sequence analysis

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

Related Items

The density maximization problem in graphs, Optimal algorithms for the average-constrained maximum-sum segment problem, An optimal algorithm for the maximum-density path in a tree

Uses Software

• MAVG
• SEGID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient algorithm for the length-constrained heaviest path problem on a tree
• Finding a longest nonnegative path in a constant degree tree
• Linear-time algorithm for finding a maximum-density segment of a sequence
• Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• An optimal algorithm for selection in a min-heap
• On the range maximum-sum segment query problem
• Improved algorithms for the \(k\) maximum-sums problems
• Fast Algorithms for Finding Nearest Common Ancestors
• ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS
• Data Mining with optimized two-dimensional association rules
• A Linear Time Algorithm for the k Maximal Sums Problem
• An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Finding the k Shortest Paths
• Spanning Trees and Optimization Problems
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Finding kth paths and p-centers by generating and searching good data structures
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem
• Efficient Algorithms for the Sum Selection Problem and K Maximum Sums Problem
• Algorithms and Computation
• Computing and Combinatorics
• Algorithms and Computation