39 citations · 255 across the 76 of their papers we have counts for
103 papers · 1 filter
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…
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…
Better Indexing for Rectangular Pattern Matching
Paweł Gawrychowski, Adam Górkiewicz
We revisit the complexity of building, given a two-dimensional string of size , an indexing structure that allows locating all occurrences of a two-dimensional pattern of si…