On the range maximum-sum segment query problem

DOI10.1016/J.DAM.2007.05.018MaRDI QIDQ2384388zbMATH OpenOpenAlexFDO

Authors Kuan-Yu Chen, Kun-Mao Chao

Publication date 21 September 2007

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.05.018

zbMATH Keywords

least common ancestormaximum-sum segmentrange minimum query

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• Algorithms and Computation
• Two-Dimensional Range Minimum Queries
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Cache oblivious algorithms for the RMQ and the RMSQ problems
• How to answer a small batch of RMQs or LCA queries in practice

Cites work

• A unifying look at data structures
• An optimal algorithm for maximum-sum segment and its application in bioinformatics (extended abstract)
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Lowest common ancestors in trees and directed acyclic graphs
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint

Cited in

(17)

• The reverse problem of range query
• The Range 1 Query (R1Q) Problem
• Encodings of range maximum-sum segment queries and applications
• Dynamic Planar Range Maxima Queries
• An optimal algorithm for maximum-sum segment and its application in bioinformatics (extended abstract)
• Maximizing Range Sum in External Memory
• Linear time computation of the maximal linear and circular sums of multiple independent insertions into a sequence
• Computing the coarseness with strips or boxes
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Algorithms and Computation
• Cache oblivious algorithms for the RMQ and the RMSQ problems
• Shortest longest-path graph orientations
• A data structure for the maximum-sum segment problem with offsets
• Shortest longest-path graph orientations
• Left-bottom and right-top segments
• Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence
• Optimal algorithms for the average-constrained maximum-sum segment problem

Describes a project that uses

Uses Software

• SEGID
• MAVG

This page was built for publication: On the range maximum-sum segment query problem

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