39 citations · 255 across the 76 of their papers we have counts for
5 papers · 1 filter
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
Given a signed permutation on elements, we need to sort it with the fewest reversals. This is a fundamental algorithmic problem motivated by applications in comparative genomic…
Compressed Indexing for Consecutive Occurrences
Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya +1
The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient s…
Optimal Square Detection Over General Alphabets
Jonas Ellert, Paweł Gawrychowski, Garance Gourdel
Squares (fragments of the form , for some string ) are arguably the most natural type of repetition in strings. The basic algorithmic question concerning squares is to check…
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…
Order-Preserving Squares in Strings
Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau
An order-preserving square in a string is a fragment of the form where and is order-isomorphic to . We show that a string of length over an alphabet o…