Compressed range minimum queries
From MaRDI portal
Publication:2297849
DOI10.1016/j.tcs.2019.07.002zbMath1435.68069arXiv1902.04427OpenAlexW2954607443WikidataQ127552079 ScholiaQ127552079MaRDI QIDQ2297849
Shay Mozes, Seungbum Jo, Oren Weimann, Paweł Gawrychowski
Publication date: 20 February 2020
Published in: Theoretical Computer Science, String Processing and Information Retrieval (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1902.04427
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Data structures (68P05) Algorithms on strings (68W32)
Related Items
Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Balancing straight-line programs for strings and trees
Cites Work
- Approximation of smallest linear tree grammar
- On Cartesian trees and range minimum queries
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Practical compressed suffix trees
- Tree compression using string grammars
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Tree compression with top trees
- On succinct representations of binary trees
- Fast \(q\)-gram mining on SLP compressed strings
- Maintaining information in fully dynamic trees with top trees
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Grammar-Based Tree Compression
- The Smallest Grammar Problem
- A unifying look at data structures
- Variations on the Common Subexpression Problem
- Balancing Straight-line Programs
- A Space-Optimal Grammar Compression.
- Slowing Down Top Trees for Better Worst-Case Compression
- Random Access to Grammar-Compressed Strings and Trees
