Tomasz Kociumaka

I am a PhD student of Computer Science at the Institute of Informatics, University of Warsaw.

Contact

E-mail address: kociumaka@mimuw.edu.pl
Public PGP key

Papers

See also at DBLP and Google Scholar.
Order by
Filter

A linear time algorithm for seeds computation [DOI] [arXiv] [slides]
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Wavelet trees meet suffix trees [DOI] [arXiv] [slides]
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka and Tatiana Starikovskaya
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Internal pattern matching queries in a text and applications [DOI] [arXiv] [slides]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Sparse suffix tree construction in optimal time and space [DOI] [arXiv]
Paweł Gawrychowski and Tomasz Kociumaka
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Hardness of approximation for strip packing [arXiv]
Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk and Michał Pilipczuk
ACM Transactions on Computation Theory

Fast algorithm for partial covers in words [DOI]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithmica

String Powers in Trees [DOI]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithmica

Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Algorithmica

Efficient indexes for jumbled pattern matching with constant-sized alphabet [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Algorithms - ESA 2013

Sublinear space algorithms for the Longest Common Substring problem [DOI] [arXiv] [pdf]
Tomasz Kociumaka, Tatiana Starikovskaya and Hjalte Wedel Vildhøj
Algorithms - ESA 2014

Approximating LZ77 via small-space multiple-pattern matching [DOI] [arXiv] [pdf]
Johannes Fischer, Travis Gagie, Paweł Gawrychowski and Tomasz Kociumaka
Algorithms - ESA 2015

Efficient counting of square substrings in a tree [DOI] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithms and Computation, ISAAC 2012

Covering problems for partial words and for indeterminate strings [DOI] [pdf] [slides]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithms and Computation, ISAAC 2014

Pattern matching and consensus problems on weighted sequences and profiles [DOI] [arXiv] [slides]
Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Algorithms and Computation, ISAAC 2016

Universal reconstruction of a string [DOI] [pdf] [slides]
Paweł Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Algorithms and Data Structures, WADS 2015

Approximating upper degree-constrained partial orientations [DOI] [arXiv] [pdf] [slides]
Marek Cygan and Tomasz Kociumaka
Approximation, Randomization, and Combinatorial Optimization APPROX/RANDOM 2015

The maximum number of squares in a tree [DOI] [pdf] [slides]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczyński and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2012

Fast algorithm for partial covers in words [DOI] [pdf] [slides]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2013

Computing minimal and maximal suffixes of a substring revisited [DOI] [pdf]
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka and Tatiana Starikovskaya
Combinatorial Pattern Matching, CPM 2014

Efficient algorithms for shortest partial seeds in words [DOI] [pdf] [slides]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2014

Computing k-th Lyndon word and decoding lexicographically minimal de Bruijn sequence [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Combinatorial Pattern Matching, CPM 2014

String powers in trees [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2015

Efficient index for weighted sequences [DOI] [arXiv] [slides]
Carl Barton, Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Combinatorial Pattern Matching, CPM 2016

Faster longest common extension queries in strings over general alphabets [DOI] [arXiv]
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2016

Minimal suffix and rotation of a substring in optimal time [DOI] [arXiv] [slides]
Tomasz Kociumaka
Combinatorial Pattern Matching, CPM 2016

A fast branching algorithm for Cluster Vertex Deletion [DOI] [pdf] [slides]
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka and Marcin Pilipczuk
Computer Science Symposium in Russia, CSR 2014

Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes [DOI] [pdf]
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Computing and Combinatorics, COCOON 2017

Maximum number of distinct and nonequivalent nonstandard squares in a word [DOI] [arXiv] [pdf]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Developments in Language Theory, DLT 2014

Algorithmics of repetitions, local periods and critical factorization revisited [URL]
Maxime Crochemore, Tomasz Kociumaka, Wojciech Rytter, Chalita Toopsuwan, Wojciech Tyczyński and Tomasz Waleń
Festschrift for Bořivoj Melichar

A note on efficient computation of all Abelian periods in a string [DOI] [arXiv] [pdf]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczyński and Tomasz Waleń
Information Processing Letters

On the greedy algorithm for the Shortest Common Superstring problem with reversals [DOI] [arXiv]
Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Information Processing Letters

An LP-rounding 22-approximation for restricted maximum acyclic subgraph [DOI] [arXiv] [pdf]
Fabrizio Grandoni, Tomasz Kociumaka and Michał Włodarczyk
Information Processing Letters

Faster deterministic Feedback Vertex Set [DOI] [arXiv] [pdf]
Tomasz Kociumaka and Marcin Pilipczuk
Information Processing Letters

Fast algorithms for Abelian periods in words and greatest common divisor queries [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Journal of Computer and System Sciences

A note on the longest common compatible prefix problem for partial words [DOI] [arXiv]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder and Tomasz Waleń
Journal of Discrete Algorithms

Linear-time version of Holub's algorithm for morphic imprimitivity testing [DOI] [pdf]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Language and Automata Theory and Applications, LATA 2013

Subquadratic-time algorithms for Abelian stringology problems [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Bartłomiej Wiśniewski
Mathematical Aspects of Computer and Information Sciences, MACIS 2015

New and efficient approaches to the quasiperiodic characterisation of a string [URL]
Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth and Wojciech Tyczyński
Prague Stringology Conference 2012

Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
SIAM Journal on Discrete Mathematics

Efficient data structures for the factor periodicity problem [DOI] [pdf] [slides]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2012

Order-preserving incomplete suffix trees and order-preserving indexes [DOI] [arXiv] [pdf]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2013

On the String Consensus problem and the Manhattan Sequence Consensus problem [DOI] [arXiv] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2014

Efficient algorithms for longest closed factor array [DOI] [pdf]
Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2015

Tight bound for the number of distinct palindromes in a tree [DOI] [pdf]
Paweł Gawrychowski, Tomasz Kociumaka, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2015

Near-optimal computation of runs over general alphabet via non-crossing LCE queries [DOI] [arXiv] [slides]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
String Processing and Information Retrieval, SPIRE 2016

On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation [arXiv]
Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon J. Puglisi
String Processing and Information Retrieval, SPIRE 2017

Linear search by a pair of distinct-speed robots [DOI] [pdf]
Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka and Dominik Pająk
Structural Information and Communication Complexity, SIROCCO 2016

Constant factor approximation for Capacitated k-Center with Outliers [DOI] [arXiv] [slides]
Marek Cygan and Tomasz Kociumaka
Symposium on Theoretical Aspects of Computer Scienc, STACS 2014

Fast algorithms for Abelian periods in words and greatest common divisor queries [DOI] [slides]
Tomasz Kociumaka, Jakub Radoszewski and Wojciech Rytter
Symposium on Theoretical Aspects of Computer Science, STACS 2013

Computing minimal and maximal suffixes of a substring [DOI] [arXiv]
Maxim Babenko, Paweł Gawrychowski, Tomasz Kociumaka, Ignat Kolesnichenko and Tatiana Starikovskaya
Theoretical Computer Science

Order-preserving indexing [DOI]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Covering problems for partial words and for indeterminate strings [DOI] [arXiv]
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Fast computation of Abelian runs [DOI] [arXiv]
Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre and Élise Prieur-Gaston
Theoretical Computer Science

Enhanced string covering [DOI] [arXiv]
Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth and Wojciech Tyczyński
Theoretical Computer Science

Efficient counting of square substrings in a tree [DOI] [pdf]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Linear-time version of Holub's algorithm for morphic imprimitivity testing [DOI]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Maximum number of distinct and nonequivalent nonstandard squares in a word [DOI]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

On the string consensus problem and the Manhattan sequence consensus problem [DOI]
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

Efficient algorithms for shortest partial seeds in words [DOI]
Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Theoretical Computer Science

A fast branching algorithm for cluster vertex deletion [DOI] [arXiv]
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka and Marcin Pilipczuk
Theory of Computing Systems

Indexing Weighted Sequences: Neat and Efficient [arXiv]
Carl Barton, Tomasz Kociumaka, Chang Liu, Solon P. Pissis and Jakub Radoszewski

Deleting vertices to graphs of bounded genus [arXiv]
Tomasz Kociumaka and Marcin Pilipczuk

Optimal dynamic strings [arXiv] [slides]
Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki and Piotr Sankowski