A simple linear-space data structure for constant-time range minimum query
From MaRDI portal
Publication:1740692
DOI10.1016/j.tcs.2018.10.019zbMath1473.68059arXiv1109.4460OpenAlexW2904368314WikidataQ129023513 ScholiaQ129023513MaRDI QIDQ1740692
Stephane Durocher, Robby Singh
Publication date: 2 May 2019
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1109.4460
Related Items
Encodings of Range Maximum-Sum Segment Queries and Applications, Linear-time superbubble identification algorithm for genome assembly, Efficient semi-external depth-first search, Linear-space data structures for range minority query in arrays, A simple linear-space data structure for constant-time range minimum query, Efficient dynamic range minimum query, Linear-space data structures for range mode query in arrays, Array Range Queries, Linear-space data structures for range frequency queries on arrays and trees
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On space efficient two dimensional range minimum data structures
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Encoding 2D range maximum queries
- Succinct data structures for flexible text retrieval systems
- Preserving order in a forest in less than logarithmic time and linear space
- A simple linear-space data structure for constant-time range minimum query
- Array Range Queries
- Succinct Representations of Binary Trees for Range Minimum Queries
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Fast Algorithms for Finding Nearest Common Ancestors
- A Compressed Enhanced Suffix Array Supporting Fast String Matching
- Two-Dimensional Range Minimum Queries
- Optimal Succinctness for Range Minimum Queries
- 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
- Recursive Star-Tree Parallel Data Structure
- Path Minima Queries in Dynamic Weighted Trees
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- STACS 2005
- Lowest common ancestors in trees and directed acyclic graphs