From the 2 of 11 linked papers with an AI index.
11 papers
String Matching in (Block) Graphs: A Full Classification by Walk Length
Sebastian Angrick, Ben Bals, PaweÅ Gawrychowski +2
The paper classifies the computational complexity of finding a walk with a given pattern in directed graphs whose nodes are labeled by strings, focusing on walks that traverse a bo…
Random Access to LZ-End: Faster and Deterministic
Itai Boneh, PaweÅ Gawrychowski
The paper presents a deterministic, O(z)-space data structure for LZ-End compressed strings that supports random access and substring extraction queries in polylogarithmic time, wi…
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…
Dynamic Longest Common Substring in Polylogarithmic Time
Panagiotis Charalampopoulos, PaweÅ Gawrychowski, Karol Pokorski
The longest common substring problem consists in finding a longest string that appears as a (contiguous) substring of two input strings. We consider the dynamic variant of this pro…
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,…