Weighted edit distance computation: strings, trees, and Dyck
From MaRDI portal
Publication:6499236
DOI10.1145/3564246.3585178MaRDI QIDQ6499236FDOQ6499236
Authors: Debarati Das, Jacob Gilbert, Mohammad T. Hajiaghayi, Tomasz Kociumaka, Barna Saha
Publication date: 8 May 2024
Cites Work
- Title not available (Why is that?)
- Algorithms on Strings, Trees and Sequences
- Title not available (Why is that?)
- Compressing and indexing labeled trees, with applications
- A Minimum Distance Error-Correcting Parser for Context-Free Languages
- Approximately matching context-free languages
- The Tree-to-Tree Correction Problem
- The String-to-String Correction Problem
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- A survey on tree edit distance and related problems
- Title not available (Why is that?)
- Uniqueness Theorems for Periodic Functions
- An \(O(ND)\) difference algorithm and its variations
- Fast Algorithms for Finding Nearest Common Ancestors
- Incremental String Comparison
- Internal pattern matching queries in a text and applications
- The ``runs theorem
- Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
- Algorithms for approximate string matching
- A graph distance metric based on the maximal common subgraph
- Title not available (Why is that?)
- Combinatorial Pattern Matching
- On the sorting-complexity of suffix tree construction
- An optimal decomposition algorithm for tree edit distance
- A sublinear algorithm for weakly approximating edit distance
- Approximating edit distance in near-linear time
- Polylogarithmic approximation for edit distance and the asymmetric query complexity
- Fast string matching with k differences
- The tree-to-tree editing problem
- If the current clique algorithms are optimal, so is Valiant's parser
- Does preprocessing help in fast sequence comparisons?
- \(1+\varepsilon\) approximation of tree edit distance in quadratic time
- Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
- Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
- Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Near-optimal quantum algorithms for string problems
- Constant-factor approximation of near-linear edit distance in near-linear time
- Constant factor approximations to edit distance on far input pairs in nearly linear time
- Improved bounds for rectangular monotone min-plus product and applications
- Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)
- Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
- Near-linear time insertion-deletion codes and \((1+\varepsilon)\)-approximating edit distance via indexing
This page was built for publication: Weighted edit distance computation: strings, trees, and Dyck
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499236)