On space efficient two dimensional range minimum data structures
From MaRDI portal
Publication:692632
DOI10.1007/S00453-011-9499-0zbMATH Open1254.68093OpenAlexW2071469476MaRDI QIDQ692632FDOQ692632
Authors: Gerth Stølting Brodal, Pooya Davoodi, S. Srinivasa Rao 
Publication date: 6 December 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9499-0
Recommendations
- On space efficient two dimensional range minimum data structures
- The Encoding Complexity of Two Dimensional Range Minimum Data Structures
- Two-Dimensional Range Minimum Queries
- Data structures for range minimum queries in multidimensional arrays
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Range minimum queries in minimal space
- Tight space bounds for two-dimensional approximate range counting
- Linear-space data structures for range minority query in arrays
- Linear-space data structures for range minority query in arrays
- Linear space data structures for two types of range search
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Optimal succinctness for range minimum queries
- On Cartesian Trees and Range Minimum Queries
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lowest common ancestors in trees and directed acyclic graphs
- Compressed suffix trees with full functionality
- Finding dominators revisited (extended abstract)
- Succinct data structures for flexible text retrieval systems
- Decomposable searching problems
- Fast Algorithms for Finding Nearest Common Ancestors
- Space-Efficient Algorithms for Document Retrieval
- Two-Dimensional Range Minimum Queries
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- A unifying look at data structures
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- Data structures for range minimum queries in multidimensional arrays
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- Optimal lower bounds for rank and select indexes
- Title not available (Why is that?)
- Lempel-Ziv factorization using less time \& space
- Replacing suffix trees with enhanced suffix arrays
- The cell probe complexity of succinct data structures
- Title not available (Why is that?)
- An(other) Entropy-Bounded Compressed Suffix Tree
- Dynamic orthogonal range queries in OLAP.
- Dominance made simple
Cited In (23)
- Two-Dimensional Range Minimum Queries
- Space efficient data structures for nearest larger neighbor
- The effective entropy of next/previous larger/smaller value queries
- Succinct indices for path minimum, with applications
- On space efficient two dimensional range minimum data structures
- Space efficient data structures for nearest larger neighbor
- On hardness of several string indexing problems
- Two dimensional range minimum queries and Fibonacci lattices
- Array range queries
- Reporting and counting maximal points in a query orthogonal rectangle
- Range minimum query indexes in higher dimensions
- Encoding two-dimensional range top-\(k\) queries revisited
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- The range 1 query (R1Q) problem
- Succinct encodings for families of interval graphs
- Fast string dictionary lookup with one error
- Orthogonal range searching for text indexing
- The Encoding Complexity of Two Dimensional Range Minimum Data Structures
- Encoding two-dimensional range top-\(k\) queries
- Data structures for range minimum queries in multidimensional arrays
- Time-space trade-offs for longest common extensions
- Two Dimensional Range Minimum Queries and Fibonacci Lattices
- Algorithms and hardness for the longest common subsequence of three strings and related problems
This page was built for publication: On space efficient two dimensional range minimum data structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692632)
