Cover Image

Optimal-Time Mapping in Run-Length Compressed PBWT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bonizzoni, Paola, Cozzi, Davide, Gao, Younan
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Constructing Suffixient Arrays Revisited
by: Bonizzoni, Paola, et al.
Published: (2026)

Faster Iterative $ϕ$ Queries on the Positional BWT
by: Bonizzoni, Paola, et al.
Published: (2026)

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

Compressed Dictionary Matching on Run-Length Encoded Strings
by: Bille, Philip, et al.
Published: (2025)

An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT
by: Sanaullah, Ahsan, et al.
Published: (2025)

Counting on General Run-Length Grammars
by: Navarro, Gonzalo, et al.
Published: (2024)

Longest Unbordered Factors on Run-Length Encoded Strings
by: Sekizaki, Shoma, et al.
Published: (2025)

On Computing the Dollo-1 phylogeny in polynomial time
by: Bonizzoni, Paola, et al.
Published: (2016)

On recognizing graphs representing Persistent Perfect Phylogenies
by: Bonizzoni, Paola, et al.
Published: (2025)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
by: Kempa, Dominik, et al.
Published: (2023)

Dynamic Suffix Array in Optimal Compressed Space
by: Nishimoto, Takaaki, et al.
Published: (2024)

Edge-Minimum Walk of Modular Length in Polynomial Time
by: Amarilli, Antoine, et al.
Published: (2024)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
by: Ganczorz, Adam, et al.
Published: (2025)

Sketching and Streaming for Dictionary Compression
by: Becker, Ruben, et al.
Published: (2023)

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space
by: Nishimoto, Takaaki, et al.
Published: (2026)

Compressing Suffix Trees by Path Decompositions
by: Becker, Ruben, et al.
Published: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Optimal-Time Move Structure Construction
by: Brown, Nathaniel K., et al.
Published: (2026)

Time-Optimal Directed q-Analysis
by: Windisch, Felix, et al.
Published: (2025)

Suffixient Arrays: a New Efficient Suffix Array Compression Technique
by: Cenzato, Davide, et al.
Published: (2024)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
by: Duyster, Anouk, et al.
Published: (2026)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
by: Haeupler, Bernhard, et al.
Published: (2025)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
by: Duyster, Anouk, et al.
Published: (2025)

Fast Computation of $k$-Runs, Parameterized Squares, and Other Generalised Squares
by: Nakashima, Yuto, et al.
Published: (2025)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Deterministic $k$-Median Clustering in Near-Optimal Time
by: Costa, Martín, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Online Distributed Queue Length Estimation
by: Bhaskara, Aditya, et al.
Published: (2025)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

Compressed Index with Construction in Compressed Space
by: Kosolobov, Dmitry
Published: (2026)

Wagner's Algorithm Provably Runs in Subexponential Time for SIS$^\infty$
by: Ducas, Léo, et al.
Published: (2025)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
by: Papadopoulos, Kleitos
Published: (2026)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

Planar Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2025)

Simple Length-Constrained Minimum Spanning Trees
by: Hershkowitz, D Ellis, et al.
Published: (2024)

LZ78 Substring Compression in Compressed Space
by: Shibata, Hiroki, et al.
Published: (2025)

Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space
by: Kosolobov, Dmitry, et al.
Published: (2021)