39 citations · 255 across the 76 of their papers we have counts for
115 papers
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2
We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graph…
Random Access to LZ-End: Faster and Deterministic
Itai Boneh, Paweł Gawrychowski
The LZ-End parsing of a length- string is a variation of Lempel-Ziv compression introduced by Kreft and Navarro [DCC 2010], motivated by the lack of a linear-size structure with…
Near-Optimal and Efficient Encoding for Two-Dimensional Range Minimum Queries
Paweł Gawrychowski, Adam Górkiewicz, Srinivasa Rao Satti
We consider the 2D RMQ encoding problem: given an array of elements over a total order, encode it such that, for any query rectangle, the position of its maximum e…
Enumerating All Directed Spanning Trees in Optimal Time
Paweł Gawrychowski, Marcin Knapik
We consider the problem of enumerating, for a given directed graph and a node , all directed spanning trees of rooted at . For undirected graphs, the corre…
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs
Jie Gao, Pawel Gawrychowski, Panos Giannopoulos +4
A \emph{disk graph} is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs,…
Balancing Two-Dimensional Straight-Line Programs
Itai Boneh, Estéban Gabory, Paweł Gawrychowski +1
We consider building, given a straight-line program (SLP) consisting of productions deriving a two-dimensional string of size , a structure capable of providing…