Cover Image

Space-efficient SLP encoding for $O(\log N)$-time random access

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Takasaka, Akito, I, Tomohiro
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
by: Adudodla, Ankith Reddy, et al.
Published: (2025)

Word Break on SLP-Compressed Texts
by: De, Rajat, et al.
Published: (2025)

An $\mathcal{O}(\log N)$ Time Algorithm for the Generalized Egg Dropping Problem
by: Papadopoulos, Kleitos
Published: (2026)

Differentially Private Selection using Smooth Sensitivity
by: Yamamoto, Akito, et al.
Published: (2024)

Finding a solution to the Erdős-Ginzburg-Ziv theorem in $O(n\log\log\log n)$ time
by: Leung, Yui Hin Arvin
Published: (2025)

Space/time-efficient RDF stores based on circular suffix sorting
by: Brisaboa, Nieves R., et al.
Published: (2020)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Fully dynamic biconnectivity in $\tilde{\mathcal{O}}(\log^2 n)$ time
by: Holm, Jacob, et al.
Published: (2025)

R-enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies
by: Kimura, Kotaro, et al.
Published: (2025)

Almost succinct representation of maximal palindromes
by: Mieno, Takuya, et al.
Published: (2025)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
by: Soma, Tasuku, et al.
Published: (2025)

Inverting Parameterized Burrows-Wheeler Transform
by: Kawanami, Shogen, et al.
Published: (2025)

On the Smallest Size of Internal Collage Systems
by: Migita, Soichiro, et al.
Published: (2025)

Height-bounded Lempel-Ziv encodings
by: Bannai, Hideo, et al.
Published: (2024)

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
by: Chang, Hsien-Chih, et al.
Published: (2024)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
by: Kempa, Dominik, et al.
Published: (2025)

Adaptive encodings for small and fast compressed suffix arrays
by: Díaz-Domínguez, Diego, et al.
Published: (2026)

Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
by: Jo, Seungbum, et al.
Published: (2022)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
by: Kolmogorov, Vladimir
Published: (2023)

Building a Balanced k-d Tree in O(kn log n) Time
by: Brown, Russell A.
Published: (2014)

An O(1) Space Algorithm for N-Dimensional Tensor Rotation: A Generalization of the Reversal Method
by: Chen, Dexin
Published: (2025)

Online Matching with Delays and Size-based Costs
by: Kawase, Yasushi, et al.
Published: (2024)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

The adaptive complexity of parallelized log-concave sampling
by: Zhou, Huanjian, et al.
Published: (2024)

Space-Efficient Quantum Error Reduction without log Factors
by: Belovs, Aleksandrs, et al.
Published: (2025)

Incongruity-sensitive access to highly compressed strings
by: Cicalese, Ferdinando, et al.
Published: (2026)

A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a $K_4$-Minor
by: Groenland, Carla, et al.
Published: (2024)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
by: Hermelin, Danny, et al.
Published: (2025)

Structural Parameterizations of the Biclique-Free Vertex Deletion Problem
by: Goldmann, Lito, et al.
Published: (2023)

Determinantal Sieving
by: Eiben, Eduard, et al.
Published: (2023)

FPT algorithms over linear delta-matroids with applications
by: Eiben, Eduard, et al.
Published: (2025)

Faster PBWT prefix-array access via batching
by: Gagie, Travis
Published: (2026)

Space-time Trade-offs for the LCP Array of Wheeler DFAs
by: Cotumaccio, Nicola, et al.
Published: (2023)

Cover time of random subgraphs of the hypercube
by: Cooper, Colin, et al.
Published: (2025)

Dynamic direct (ranked) access of MSO query evaluation over SLP-compressed strings
by: Muñoz, Martín
Published: (2026)

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
by: Papadopoulos, Kleitos
Published: (2025)

Holonomic equations and efficient random generation of binary trees
by: Lescanne, Pierre
Published: (2022)

Space-efficient B-tree Implementation for Memory-Constrained Flash Embedded Devices
by: Ould-Khessal, Nadir, et al.
Published: (2026)