Cover Image

NP-Completeness for the Space-Optimality of Double-Array Tries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bannai, Hideo, Goto, Keisuke, Kanda, Shunsuke, Köppl, Dominik
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

Bijective BWT based compression schemes
by: Badkobeh, Golnaz, et al.
Published: (2024)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

Counting distinct (non-)crossing substrings
by: Umezaki, Haruki, et al.
Published: (2025)

Faster Space-Efficient STR-IC-LCS Computation
by: Yonemoto, Yuki, et al.
Published: (2022)

String Representation in Suffixient Set Size Space
by: Shibata, Hiroki, et al.
Published: (2026)

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

Online Computation of Palindromes and Suffix Trees on Tries
by: Shibata, Hiroki, et al.
Published: (2026)

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

Constant-time edge label and leaf pointer maintenance on sliding suffix trees
by: Leonard, Laurentius, et al.
Published: (2023)

Substring Compression Variations and LZ78-Derivates
by: Köppl, Dominik
Published: (2024)

LZD-style Compression Scheme with Truncation and Repetitions
by: Götz, Linus, et al.
Published: (2025)

Near-real-time Solutions for Online String Problems
by: Köppl, Dominik, et al.
Published: (2026)

Smallest suffixient set maintenance in near-real-time
by: Köppl, Dominik, et al.
Published: (2026)

Computing maximal palindromes in non-standard matching models
by: Mieno, Takuya, et al.
Published: (2022)

Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It
by: Osterkamp, Eric M., et al.
Published: (2024)

On the Number of Non-equivalent Parameterized Squares in a String
by: Hamai, Rikuya, et al.
Published: (2024)

Nyldon Factorization of Thue-Morse Words and Fibonacci Words
by: Kishi, Kaisei, et al.
Published: (2025)

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

Sensitivity of Repetitiveness Measures to String Reversal
by: Bannai, Hideo, et al.
Published: (2026)

On the compressiveness of the Burrows-Wheeler transform
by: Bannai, Hideo, et al.
Published: (2024)

Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)

On Occurrence-Preserving Morphisms
by: Kishi, Kaisei, et al.
Published: (2026)

Algorithms for Galois Words: Detection, Factorization, and Rotation
by: Hendrian, Diptarama, et al.
Published: (2024)

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

Engineering faster double-array Aho-Corasick automata
by: Kanda, Shunsuke, et al.
Published: (2022)

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

DNA Probe Computing System for Solving NP-Complete Problems
by: Xu, Jin, et al.
Published: (2025)

Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
by: Sinhal, Anay, et al.
Published: (2026)

Indexing Tries within Entropy-Bounded Space
by: Carfagna, Lorenzo, et al.
Published: (2025)

Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
by: Bentert, Matthias, et al.
Published: (2025)

Revisiting the Sparse Matrix Compression Problem
by: Jugé, Vincent, et al.
Published: (2026)

Space-Efficient Online Computation of String Net Occurrences
by: Mieno, Takuya, et al.
Published: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Linear-size Suffix Tries and Linear-size CDAWGs Simplified and Improved
by: Inenaga, Shunsuke
Published: (2024)

In-Place BWT and Lyndon Array Construction in Constant Space
by: Louza, Felipe A., et al.
Published: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

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

Engineering Optimal Parallel Task Scheduling
by: Akram, Matthew, et al.
Published: (2024)