39 citations · 255 across the 76 of their papers we have counts for
7 papers · 1 filter
Faster two-dimensional pattern matching with mismatches
Jonas Ellert, Paweł Gawrychowski, Adam Górkiewicz +1
The classical pattern matching asks for locating all occurrences of one string, called the pattern, in another, called the text, where a string is simply a sequence of characters.…
Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
Pawel Gawrychowski, Florin Manea, Markus L. Schmid
Information extraction from textual data, where the query is represented by a finite transducer and the task is to enumerate all results without repetition, and its extension to th…
Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
Paweł Gawrychowski, Egor Gorbachev, Tomasz Kociumaka
Min-plus matrix multiplication is used in many problems operating on distances in graphs or solvable by dynamic programming. Assuming the APSP hypothesis, there is no subcubic-time…
Optimal Distance Labeling for Permutation Graphs
Paweł Gawrychowski, Wojciech Janczewski
A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation on elements, such that …
Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
Paweł Gawrychowski, Mateusz Wasylkiewicz
Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither const…
Optimal Bounds for Distinct Quartics
Panagiotis Charalampopoulos, Paweł Gawrychowski, Samah Ghazawi
A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the…