5 papers
Faster ED-String Matching with Mismatches
Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak +2
We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of finite sets of strings of total length , and compac…
Optimal Heaviest Induced Ancestors
Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski +1
We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. L…
Sublinear Dynamic Interval Scheduling (on one or multiple machines)
Paweł Gawrychowski, Karol Pokorski
We revisit the complexity of the classical Interval Scheduling in the dynamic setting. In this problem, the goal is to maintain a set of intervals under insertions and deletions an…
Strictly In-Place Algorithms for Permuting and Inverting Permutations
Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski
We revisit the problem of permuting an array of length according to a given permutation in place, that is, using only a small number of bits of extra storage. Fich, Munro and P…
Dynamic Longest Common Substring in Polylogarithmic Time
Panagiotis Charalampopoulos, Paweł Gawrychowski, Karol Pokorski
The longest common substring problem consists in finding a longest string that appears as a (contiguous) substring of two input strings. We consider the dynamic variant of this pro…