39 citations · 241 across the 54 of their papers we have counts for
6 papers · 1 filter
Longest common substring with approximately mismatches
Tomasz Kociumaka, Jakub Radoszewski, Tatiana Starikovskaya
In the longest common substring problem, we are given two strings of length and must find a substring of maximal length that occurs in both strings. It is well known that the p…
The streaming -mismatch problem
Raphaël Clifford, Tomasz Kociumaka, Ely Porat
We consider the streaming complexity of a fundamental task in approximate pattern matching: the -mismatch problem. It asks to compute Hamming distances between a pattern of leng…
Deleting vertices to graphs of bounded genus
Tomasz Kociumaka, Marcin Pilipczuk
We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time $2^{C_g \cdot k^2…
On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation
Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga +3
We investigate two closely related LZ78-based compression schemes: LZMW (an old scheme by Miller and Wegman) and LZD (a recent variant by Goto et al.). Both LZD and LZMW naturally…
Indexing Weighted Sequences: Neat and Efficient
Carl Barton, Tomasz Kociumaka, Chang Liu +2
In a \emph{weighted sequence}, for every position of the sequence and every letter of the alphabet a probability of occurrence of this letter at this position is specified. Weighte…
Maximal Unbordered Factors of Random Strings
Patrick Hagge Cording, Travis Gagie, Mathias Bæk Tejs Knudsen +1
A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border other than itself. Loptev, Kucherov, an…