39 citations · 255 across the 76 of their papers we have counts for
10 papers · 1 filter
The complexity of mean payoff games using universal graphs
Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann
We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in bot…
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes +1
We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are w…
Computing Quartet Distance is Equivalent to Counting 4-Cycles
Bartłomiej Dudek, Paweł Gawrychowski
The quartet distance is a measure of similarity used to compare two unrooted phylogenetic trees on the same set of leaves, defined as the number of subsets of four leaves relat…
Fast and Longest Rollercoasters
Paweł Gawrychowski, Florin Manea, Radosław Serafin
For , a k-rollercoaster is a sequence of numbers whose every maximal contiguous subsequence, that is increasing or decreasing, has length at least ; -rollercoasters…
Streaming dictionary matching with mismatches
Paweł Gawrychowski, Tatiana Starikovskaya
In the -mismatch problem we are given a pattern of length and a text and must find all locations where the Hamming distance between the pattern and the text is at most .…
Near-Optimal Distance Emulator for Planar Graphs
Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes +1
Given a graph and a set of terminals , a \emph{distance emulator} of is another graph (not necessarily a subgraph of ) containing , such that all the pairwise…