Copertina

Linear-space LCS enumeration with quadratic-time delay for two strings

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Sakai, Yoshifumi
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the Complexity of Finding Approximate LCS of Multiple Strings
di: Hasibi, Hamed, et al.
Pubblicazione: (2025)

Subsequence Matching and LCS with Segment Number Constraints
di: Yonemoto, Yuki, et al.
Pubblicazione: (2024)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
di: Tsujimoto, Taketo, et al.
Pubblicazione: (2024)

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

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
di: Mao, Xiao, et al.
Pubblicazione: (2026)

Constant delay Gray code enumeration of ideals and antichains in posets
di: Brenner, Sofia, et al.
Pubblicazione: (2026)

Constant time enumeration of perfect bipartite matchings
di: Fink, Jiří
Pubblicazione: (2025)

Ultrabubble enumeration via a lowest common ancestor approach
di: Zisis, Athanasios E., et al.
Pubblicazione: (2026)

BWT for string collections
di: Cenzato, Davide, et al.
Pubblicazione: (2025)

An algorithm with a delay of $\mathcal{O}(kΔ)$ for enumerating connected induced subgraphs of size $k$
di: Xiao, Chenglong, et al.
Pubblicazione: (2024)

Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time
di: Lancia, Giuseppe, et al.
Pubblicazione: (2024)

Online matching with delays and stochastic arrival times
di: Mari, Mathieu, et al.
Pubblicazione: (2022)

A survey of BWT variants for string collections
di: Cenzato, Davide, et al.
Pubblicazione: (2022)

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

Simple Linear-time Repetition Factorization
di: Yonemoto, Yuki, et al.
Pubblicazione: (2024)

On the enumeration of signatures of XOR-CNF's
di: Creignou, Nadia, et al.
Pubblicazione: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
di: Enright, Jessica, et al.
Pubblicazione: (2020)

Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
di: Velusamy, Santhoshini
Pubblicazione: (2025)

Constant-delay enumeration for SLP-compressed documents
di: Muñoz, Martín, et al.
Pubblicazione: (2022)

Better space-time-robustness trade-offs for set reconciliation
di: Belazzougui, Djamal, et al.
Pubblicazione: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
di: Eden, Talya, et al.
Pubblicazione: (2025)

Numerical Linear Algebra in Linear Space
di: Liu, Yiping, et al.
Pubblicazione: (2025)

Non-Linear Paging
di: Doron-Arad, Ilan, et al.
Pubblicazione: (2024)

On Differentially Private Linear Algebra
di: Kaplan, Haim, et al.
Pubblicazione: (2024)

Parameterized Approximability for Modular Linear Equations
di: Dabrowski, Konrad K., et al.
Pubblicazione: (2025)

Network Unreliability in Almost-Linear Time
di: Cen, Ruoxu, et al.
Pubblicazione: (2025)

Solving Linear Programs with Differential Privacy
di: Ene, Alina, et al.
Pubblicazione: (2025)

Vizing's Theorem in Near-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Deterministic Mincut in Almost-Linear Time
di: Li, Jason
Pubblicazione: (2021)

Parameterized Linear Time Transitive Closure
di: Kritikakis, Giorgos, et al.
Pubblicazione: (2024)

Approximating Partition in Near-Linear Time
di: Chen, Lin, et al.
Pubblicazione: (2024)

Verifying Shortest Paths in Linear Time
di: Shokry, Ahmed, et al.
Pubblicazione: (2024)

On Solving Linear Systems in Sublinear Time
di: Andoni, Alexandr, et al.
Pubblicazione: (2018)

Faster Approximate Linear Matroid Intersection
di: Terao, Tatsuya
Pubblicazione: (2026)

Simple Linear-Size Additive Emulators
di: Hoppenworth, Gary
Pubblicazione: (2023)

Unbreakable Decomposition in Close-to-Linear Time
di: Anand, Aditya, et al.
Pubblicazione: (2024)

Approximating Directed Connectivity in Almost-Linear Time
di: Quanrud, Kent
Pubblicazione: (2025)

Improved Tree Sparsifiers in Near-Linear Time
di: Agassy, Daniel, et al.
Pubblicazione: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Tight Analyses of Ordered and Unordered Linear Probing
di: Braverman, Mark, et al.
Pubblicazione: (2025)