Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
In this paper, we design new sublinear-time algorithms for solving the gap edit distance problem and for embedding edit distance to Hamming distance. For the gap edit distance problem, we give an $\tilde{O}(\frac{n}{k}+k^2)$-time greedy algorithm that distinguishes between length-$n$ input strings w...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2007.12762 http://arxiv.org/abs/2007.12762 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|