39 citations · 255 across the 76 of their papers we have counts for
7 papers · 1 filter
A note on distance labeling in planar graphs
Paweł Gawrychowski, Przemysław Uznański
A distance labeling scheme is an assignments of labels, that is binary strings, to all nodes of a graph, so that the distance between any two nodes can be computed from their label…
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams
Paweł Gawrychowski, Oleg Merkurev, Arseny M. Shur +1
We consider computing a longest palindrome in the streaming model, where the symbols arrive one-by-one and we do not have random access to the input. While computing the answer exa…
Sparse Suffix Tree Construction in Optimal Time and Space
Paweł Gawrychowski, Tomasz Kociumaka
Suffix tree (and the closely related suffix array) are fundamental structures capturing all substrings of a given text essentially by storing all its suffixes in the lexicographica…
Optimal Distance Labeling Schemes for Trees
Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson +1
Labeling schemes seek to assign a short label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. For the particular case of…
Randomized algorithms for finding a majority element
Paweł Gawrychowski, Jukka Suomela, Przemysław Uznański
Given colored balls, we want to detect if more than of them have the same color, and if so find one ball with such majority color. We are only allowed to c…
Improved Bounds for Shortest Paths in Dense Distance Graphs
Paweł Gawrychowski, Adam Karczmarz
We study the problem of computing shortest paths in so-called dense distance graphs. Every planar graph on vertices can be partitioned into a set of edge-disjoint…