Tomasz Kociumaka

The streaming k-mismatch problem [arXiv]
Raphaël Clifford, Tomasz Kociumaka and Ely Porat
30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019

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

Linear-time algorithm for Long LCF with k mismatches [DOI] [arXiv]
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Combinatorial Pattern Matching, CPM 2018

Edit distance with block operations [DOI]
Michał Gańczorz, Paweł Gawrychowski, Artur Jeż and Tomasz Kociumaka
Algorithms --- ESA 2018

On Abelian Longest Common Factor with and without RLE [DOI] [arXiv]
Szymon Grabowski, Tomasz Kociumaka and Jakub Radoszewski
Fundamenta Informaticae

Longest Unbordered Factor in Quasilinear Time [arXiv]
Tomasz Kociumaka, Ritu Kundu, Manal Mohamed and Solon P. Pissis
Algorithms and Computation, ISAAC 2018

Efficient enumeration of non-equivalent squares in partial words with few holes [DOI]
Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Journal of Combinatorial Optimization

On periodicity lemma for partial words [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter and Tomasz Waleń
Language and Automata Theory and Applications, LATA 2018

Optimal dynamic strings [DOI] [arXiv] [slides]
Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki and Piotr Sankowski
29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Faster recovery of approximate periods over edit distance [DOI] [arXiv]
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba
String Processing and Information Retrieval, SPIRE 2018

Efficient computation of sequence mappability [DOI]
Mai Alzamel, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski and Juliusz Straszyński
String Processing and Information Retrieval, SPIRE 2018

String periods in the order-preserving model [DOI] [arXiv]
Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny Shur and Tomasz Waleń
Symposium on Theoretical Aspects of Computer Science, STACS 2018

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

Pattern matching and consensus problems on weighted sequences and profiles [DOI]
Tomasz Kociumaka, Solon P. Pissis and Jakub Radoszewski
Theory of Computing Systems

Subquadratic-time algorithms for Abelian stringology problems [DOI]
Tomasz Kociumaka, Jakub Radoszewski and Bartłomiej Wiśniewski
AIMS Medical Science

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

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

Longest common substring with approximately k mismatches [arXiv]
Tomasz Kociumaka, Jakub Radoszewski and Tatiana Starikovskaya

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

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

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

On two LZ78-style grammars: compression bounds and compressed-space computation [DOI] [arXiv]
Golnaz Badkobeh, Travis Gagie, Shunsuke Inenaga, Tomasz Kociumaka, Dmitry Kosolobov and Simon J. Puglisi
String Processing and Information Retrieval, SPIRE 2017

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

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

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

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

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

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

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

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

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

Fast computation of Abelian runs [DOI] [arXiv]
Gabriele Fici, Tomasz Kociumaka, Thierry Lecroq, Arnaud Lefebvre and Élise Prieur-Gaston
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

A fast branching algorithm for Cluster Vertex Deletion [DOI] [arXiv]
Anudhyan Boral, Marek Cygan, Tomasz Kociumaka and Marcin Pilipczuk
Theory of Computing Systems

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

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

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

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

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

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

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

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

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

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

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

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

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 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 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

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

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