24 citations · 145 across the 45 of their papers we have counts for
6 papers · 2 filters
Breaking the Variance: Approximating the Hamming Distance in Time Per Alignment
Tsvi Kopelowitz, Ely Porat
The algorithmic tasks of computing the Hamming distance between a given pattern of length and each location in a text of length is one of the most fundamental algorithmic t…
The k-mismatch problem revisited
Raphaël Clifford, Allyx Fontaine, Ely Porat +2
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and ev…
Distance labeling schemes for trees
Stephen Alstrup, Inge Li Gørtz, Esben Bistrup Halvorsen +1
We consider distance labeling schemes for trees: given a tree with nodes, label the nodes with binary strings such that, given the labels of any two nodes, one can determine, b…
Sublinear Distance Labeling
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen +1
A distance labeling scheme labels the nodes of a graph with binary strings such that, given the labels of any two nodes, one can determine the distance in the graph between the…
Dictionary matching in a stream
Raphael Clifford, Allyx Fontaine, Ely Porat +2
We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report…
Mind the Gap
Amihood Amir, Tsvi Kopelowitz, Avivit Levy +3
We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary of patterns, where each pattern cont…