Cache oblivious algorithms for the RMQ and the RMSQ problems

DOI10.1007/S11786-010-0037-2MaRDI QIDQ626901zbMATH OpenOpenAlexFDO

Authors Masud Hasan, Tanaeem M. Moosa, M. Sohel Rahman

Publication date 19 February 2011

Published in Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11786-010-0037-2

zbMATH Keywords

algorithmscache oblivious algorithmsrange maximum-sum segment queryrange minima/maxima query

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Algorithms and Computation
• On the range maximum-sum segment query problem
• I/O-efficient range minima queries
• On (dynamic) range minimum queries in external memory
• Data structures for range minimum queries in multidimensional arrays

Cites work

• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• An optimal algorithm for maximum-sum segment and its application in bioinformatics (extended abstract)
• An Optimal Algorithm for the Maximum-Density Segment Problem
• Cache-oblivious algorithms
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding Patterns in Given Intervals
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• On Cartesian Trees and Range Minimum Queries
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On the range maximum-sum segment query problem
• Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint
• Optimal prefix and suffix queries on texts
• Succinct data structures for flexible text retrieval systems

Cited in

(4)

• On the range maximum-sum segment query problem
• I/O-efficient range minima queries
• scientific article; zbMATH DE number 6169004 (Why is no real title available?)
• Algorithms and Computation

Describes a project that uses

Uses Software

• MAVG
• SEGID

This page was built for publication: Cache oblivious algorithms for the RMQ and the RMSQ problems

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