39 citations · 255 across the 76 of their papers we have counts for
11 papers · 1 filter
Pattern Matching on Grammar-Compressed Strings in Linear Time
Moses Ganardi, Paweł Gawrychowski
The most fundamental problem considered in algorithms for text processing is pattern matching: given a pattern of length and a text of length , does occur in …
Finding the KT partition of a weighted graph in near-linear time
Simon Apers, Paweł Gawrychowski, Troy Lee
In a breakthrough work, Kawarabayashi and Thorup (J.~ACM'19) gave a near-linear time deterministic algorithm for minimum cut in a simple graph . A key component is findi…
Faster Exponential Algorithm for Permutation Pattern Matching
Pawel Gawrychowski, Mateusz Rzepecki
The Permutation Pattern Matching problem asks, given two permutations on elements and , whether admits a subsequence with the same relative order as (or, in the…
Matching Patterns with Variables under Hamming Distance
Paweł Gawrychowski, Florin Manea, Stefan Siemer
A pattern is a string of variables and terminal letters. We say that matches a word , consisting only of terminal letters, if can be obtained by replacing the variab…
Lower Bounds for the Number of Repetitions in 2D Strings
Paweł Gawrychowski, Samah Ghazawi, Gad M. Landau
A two-dimensional string is simply a two-dimensional array. We continue the study of the combinatorial properties of repetitions in such strings over the binary alphabet, namely th…
The Dynamic k-Mismatch Problem
Raphaël Clifford, Paweł Gawrychowski, Tomasz Kociumaka +2
The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length and all length- substrings of a given text of length $n…