Many flavors of edit distance
From MaRDI portal
Cites work
- A faster algorithm computing string edit distances
- A sublinear algorithm for weakly approximating edit distance
- Approximating edit distance efficiently
- Approximating edit distance in near-linear time
- Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
- Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
- Constant factor approximations to edit distance on far input pairs in nearly linear time
- Constant-factor approximation of near-linear edit distance in near-linear time
- Does preprocessing help in fast sequence comparisons?
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Edit distance in near-linear time: it's a constant factor
- scientific article; zbMATH DE number 3133919 (Why is no real title available?)
- scientific article; zbMATH DE number 3240929 (Why is no real title available?)
- Incremental String Comparison
- Low distortion embeddings for edit distance
- New tabulation and sparse dynamic programming based techniques for sequence similarity problems
- Oblivious string embeddings and edit distance approximations
- Semi-local string comparison: algorithmic techniques and applications
- Streaming algorithms for embedding and computing edit distance in the low distance regime
- The String-to-String Correction Problem
- Tight hardness results for LCS and other sequence similarity measures
- Tighter connections between Formula-SAT and shaving logs
This page was built for publication: Many flavors of edit distance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7263568)
