Weighted edit distance computation: strings, trees, and Dyck

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)