39 citations · 241 across the 54 of their papers we have counts for
7 papers · 1 filter
Covering Problems for Partial Words and for Indeterminate Strings
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka +3
We consider the problem of computing a shortest solid cover of an indeterminate string. An indeterminate string may contain non-solid symbols, each of which specifies a subset of t…
Wavelet Trees Meet Suffix Trees
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka +1
We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n…
Approximating Upper Degree-Constrained Partial Orientations
Marek Cygan, Tomasz Kociumaka
In the Upper Degree-Constrained Partial Orientation problem we are given an undirected graph , together with two degree constraint functions .…
On the String Consensus Problem and the Manhattan Sequence Consensus Problem
Tomasz Kociumaka, Jakub W. Pachocki, Jakub Radoszewski +2
In the Manhattan Sequence Consensus problem (MSC problem) we are given integer sequences, each of length , and we are to find an integer sequence of length (called a…
Sublinear Space Algorithms for the Longest Common Substring Problem
Tomasz Kociumaka, Tatiana Starikovskaya, Hjalte Wedel Vildhøj
Given documents of total length , we consider the problem of finding a longest string common to at least of the documents. This problem is known as the \emph{long…
An LP-Rounding Approximation for Restricted Maximum Acyclic Subgraph
Fabrizio Grandoni, Tomasz Kociumaka, Michał Włodarczyk
In the classical Maximum Acyclic Subgraph problem (MAS), given a directed-edge weighted graph, we are required to find an ordering of the nodes that maximizes the total weight of f…
Constant Factor Approximation for Capacitated k-Center with Outliers
Tomasz Kociumaka, Marek Cygan
The -center problem is a classic facility location problem, where given an edge-weighted graph one is to find a subset of vertices , such that each vertex in…