4 papers
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…