Range minimum queries in minimal space

DOI10.1016/j.tcs.2022.01.025OpenAlexW4206702724MaRDI QIDQ2078612

Luís M. S. Russo

Publication date: 1 March 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.09463

zbMATH Keywords

range minimum queriesunion-findstring processingdisjoint setsbulk queries

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• The longest common extension problem revisited and applications to approximate string searching
• Succinct data structures for flexible text retrieval systems
• A linear-time algorithm for a special case of disjoint set union
• An almost optimal algorithm for unbounded searching
• How to answer a small batch of RMQs or LCA queries in practice
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Cartesian and Lyndon trees
• Improved range minimum queries
• Compressed suffix trees with full functionality
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast Intersection Algorithms for Sorted Sequences
• Worst-case Analysis of Set Union Algorithms
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Recursive Star-Tree Parallel Data Structure
• Design and implementation of an efficient priority queue
• Balanced Allocations
• Practical Range Minimum Queries Revisited
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• An improved equivalence algorithm
• Set Merging Algorithms

This page was built for publication: Range minimum queries in minimal space