19 citations · 43 across the 19 of their papers we have counts for
5 papers · 1 filter
Hardness of approximation for strip packing
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk +1
Strip packing is a classical packing problem, where the goal is to pack a set of rectangular objects into a strip of a given width, while minimizing the total height of the packing…
Sparse Suffix Tree Construction in Optimal Time and Space
Paweł Gawrychowski, Tomasz Kociumaka
Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographica…
Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +5
Longest common extension queries (LCE queries) and runs are ubiquitous in algorithmic stringology. Linear-time algorithms computing runs and preprocessing for constant-time LCE que…
Maximum Number of Distinct and Nonequivalent Nonstandard Squares in a Word
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter +1
The combinatorics of squares in a word depends on how the equivalence of halves of the square is defined. We consider Abelian squares, parameterized squares, and order-preserving s…
Pattern Matching and Consensus Problems on Weighted Sequences and Profiles
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski
We study pattern matching problems on two major representations of uncertain sequences used in molecular biology: weighted sequences (also known as position weight matrices, PWM) a…