Range minimum queries in minimal space
type: Item
instance of: scholarly article
title: Range minimum queries in minimal space
author: Luís M. S. Russo
published in: Theoretical Computer Science
publication date: 2022-03-01T00:00:00Z
full work available at URL: https://arxiv.org/abs/2102.09463
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7482352
zbMATH Keywords: range minimum queries
zbMATH Keywords: union-find
zbMATH Keywords: disjoint sets
zbMATH Keywords: bulk queries
zbMATH Keywords: string processing
MaRDI profile type: Publication
OpenAlex ID: W4206702724
cites work: How to answer a small batch of RMQs or LCA queries in practice
cites work: Q3651735
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
cites work: Worst-case Analysis of Set Union Algorithms
cites work: Balanced Allocations
cites work: Q4508365
cites work: Recursive Star-Tree Parallel Data Structure
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: On Finding Lowest Common Ancestors: Simplification and Parallelization
cites work: Cartesian and Lyndon trees
cites work: Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
cites work: The longest common extension problem revisited and applications to approximate string searching
cites work: Compressed suffix trees with full functionality
cites work: Succinct data structures for flexible text retrieval systems
cites work: Q5417613
cites work: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
cites work: Improved range minimum queries
cites work: Practical Range Minimum Queries Revisited
cites work: Q3992623
cites work: Q4091421
cites work: An improved equivalence algorithm
cites work: Set Merging Algorithms
cites work: A class of algorithms which require nonlinear time to maintain disjoint sets
cites work: Expected Length of the Longest Probe Sequence in Hash Code Searching
cites work: An almost optimal algorithm for unbounded searching
cites work: Fast Intersection Algorithms for Sorted Sequences
cites work: Q4349924
cites work: Design and implementation of an efficient priority queue
cites work: Log-logarithmic worst-case range queries are possible in space theta(N)
DOI: 10.1016/J.TCS.2022.01.025
Recommended article: Practical Range Minimum Queries Revisited
Recommended article: Optimal Succinctness for Range Minimum Queries
Recommended article: Lower bound for succinct range minimum query
Recommended article: Compressed range minimum queries
Recommended article: Two-Dimensional Range Minimum Queries
Recommended article: Q5417614
Recommended article: I/O-Efficient Range Minima Queries
Recommended article: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
description: scientific article; zbMATH DE number 7482352