9 citations · 9 across the 4 of their papers we have counts for
5 papers · 1 filter
Constant factor approximations to edit distance on far input pairs in nearly linear time
Michal Koucký, Michael E. Saks
For any , there are constants and and a randomized algorithm that takes as input an integer and two strings of length at most , an…
Approximate Online Pattern Matching in Sub-linear Time
Diptarka Chakraborty, Debarati Das, Michal Koucky
We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern of length and a text of length over some alphabet $…
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time
Diptarka Chakraborty, Debarati Das, Elazar Goldenberg +2
Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the…
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký
The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required t…
On Online Labeling with Polynomially Many Labels
Martin Babka, Jan Bulánek, Vladimír Čunát +2
In the online labeling problem with parameters n and m we are presented with a sequence of n keys from a totally ordered universe U and must assign each arriving key a label from t…