6 papers
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…
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…
Faster ED-String Matching with Mismatches
PaweŠGawrychowski, Adam Górkiewicz, Pola Marciniak +2
We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of finite sets of strings of total length , and compac…
On Incremental Approximate Shortest Paths in Directed Graphs
Adam Górkiewicz, Adam Karczmarz
In this paper, we show new data structures maintaining approximate shortest paths in sparse directed graphs with polynomially bounded non-negative edge weights under edge insertion…
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.…