Cache oblivious algorithms for the RMQ and the RMSQ problems

DOI10.1007/s11786-010-0037-2zbMath1205.68525OpenAlexW2005397752MaRDI QIDQ626901

Tanaeem M. Moosa, Masud Hasan, 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)

Uses Software

• MAVG
• SEGID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct data structures for flexible text retrieval systems
• Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint
• Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis.
• On the range maximum-sum segment query problem
• Cache-Oblivious Algorithms
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding Patterns in Given Intervals
• An Optimal Algorithm for Maximum-Sum Segment and Its Application in Bioinformatics
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• On Cartesian Trees and Range Minimum Queries
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• An Optimal Algorithm for the Maximum-Density Segment Problem

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