Name
Abstract | ||
|---|---|---|
We show that the edit distance between two run-length encoded strings of compressed lengths $m$ and $n$ respectively, can be computed in $mathcal{O}(mnlog(mn))$ time. This improves the previous record by a factor of $mathcal{O}(n/log(mn))$. The running time of our algorithm is within subpolynomial factors of being optimal, subject to the standard SETH-hardness assumption. This effectively closes a line of algorithmic research first started in 1993. |
Year | Venue | DocType |
|---|---|---|
2019 | MFCS | Journal |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël Clifford | 1 | 268 | 28.57 |
| Pawel Gawrychowski | 2 | 226 | 46.74 |
| Tomasz Kociumaka | 3 | 217 | 38.57 |
| Daniel P. Martin | 4 | 0 | 0.34 |
| Przemysław Uznański | 5 | 51 | 17.11 |