39 citations · 241 across the 54 of their papers we have counts for
7 papers · 2 filters
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…
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…
Efficient Index for Weighted Sequences
Carl Barton, Tomasz Kociumaka, Solon P. Pissis +1
The problem of finding factors of a text string which are identical or similar to a given pattern string is a central problem in computer science. A generalised version of this pro…
Faster Longest Common Extension Queries in Strings over General Alphabets
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter +1
Longest common extension queries (often called longest common prefix queries) constitute a fundamental building block in multiple string algorithms, for example computing runs and…
Minimal Suffix and Rotation of a Substring in Optimal Time
Tomasz Kociumaka
For a text given in advance, the substring minimal suffix queries ask to determine the lexicographically minimal non-empty suffix of a substring specified by the location of its oc…