Image de couverture de livre

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kociumaka, Tomasz, Shahali, Ali
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
par: Gorbachev, Egor, et autres
Publié: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
par: Boneh, Itai, et autres
Publié: (2025)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
par: Kociumaka, Tomasz, et autres
Publié: (2014)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
par: Das, Debarati, et autres
Publié: (2025)

Pattern Matching under Weighted Edit Distance
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
par: Bathie, Gabriel, et autres
Publié: (2023)

Faster Algorithms for Longest Common Substring
par: Charalampopoulos, Panagiotis, et autres
Publié: (2021)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
par: Goldenberg, Elazar, et autres
Publié: (2022)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
par: Nogler, Jakob, et autres
Publié: (2024)

The Communication Complexity of Pattern Matching with Edits Revisited
par: Kociumaka, Tomasz, et autres
Publié: (2026)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
par: Duyster, Anouk, et autres
Publié: (2026)

Tight Lower Bounds for Central String Queries in Compressed Space
par: Kempa, Dominik, et autres
Publié: (2025)

Faster Algorithms for Text-to-Pattern Hamming Distances
par: Chan, Timothy M., et autres
Publié: (2023)

Approximate Circular Pattern Matching under Edit Distance
par: Charalampopoulos, Panagiotis, et autres
Publié: (2024)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
par: Gawrychowski, Paweł, et autres
Publié: (2024)

Hardness of Dynamic Tree Edit Distance and Friends
par: Hu, Bingbing, et autres
Publié: (2025)

Many Flavors of Edit Distance
par: Bhattacharya, Sudatta, et autres
Publié: (2024)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
par: Kadria, Avi, et autres
Publié: (2025)

Near-Optimal Property Testers for Pattern Matching
par: Jin, Ce, et autres
Publié: (2025)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
par: Duyster, Anouk, et autres
Publié: (2025)

Space-Efficient k-Mismatch Text Indexes
par: Kociumaka, Tomasz, et autres
Publié: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
par: Kempa, Dominik, et autres
Publié: (2025)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
par: Kempa, Dominik, et autres
Publié: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
par: Kempa, Dominik, et autres
Publié: (2024)

Time-Optimal Construction of String Synchronizing Sets
par: Ellert, Jonas, et autres
Publié: (2026)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
par: Kempa, Dominik, et autres
Publié: (2023)

Even Faster Algorithm for the Chamfer Distance
par: Feng, Ying, et autres
Publié: (2025)

Almost Linear Size Edit Distance Sketch
par: Koucký, Michal, et autres
Publié: (2024)

On Rotation Distance of Rank Bounded Trees
par: M., Anoop S. K., et autres
Publié: (2023)

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
par: Kociumaka, Tomasz, et autres
Publié: (2024)

String Sanitization Under Edit Distance: Improved and Generalized
par: Mieno, Takuya, et autres
Publié: (2020)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
par: Mao, Xiao, et autres
Publié: (2026)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
par: Boneh, Itai, et autres
Publié: (2025)

Fully Dynamic Algorithms for Chamfer Distance
par: Goranci, Gramoz, et autres
Publié: (2025)

Exponent-Strings and Their Edit Distance
par: Baek, Ingyu
Publié: (2024)

On the Communication Complexity of Approximate Pattern Matching
par: Kociumaka, Tomasz, et autres
Publié: (2024)

Improved Algorithms for Clustering with Noisy Distance Oracles
par: Pradhan, Pinki, et autres
Publié: (2026)

Faster Algorithms for Schatten-p Low Rank Approximation
par: Kacham, Praneeth, et autres
Publié: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
par: Azarmehr, Amir, et autres
Publié: (2025)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
par: Manoharan, Vignesh, et autres
Publié: (2025)