39 citations · 255 across the 76 of their papers we have counts for
12 papers · 1 filter
Better Tradeoffs for Exact Distance Oracles in Planar Graphs
Paweł Gawrychowski, Shay Mozes, Oren Weimann +1
We present an -space distance oracle for directed planar graphs that answers distance queries in time. Our oracle both significantly simplifies and signific…
Distinct Squares in Circular Words
Mika Amit, Paweł Gawrychowski
A circular word, or a necklace, is an equivalence class under conjugation of a word. A fundamental question concerning regularities in standard words is bounding the number of dist…
Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees
Paweł Gawrychowski, Jakub Łopuszański
A labeling scheme for nearest common ancestors assigns a distinct binary string, called the label, to every node of a tree, so that given the labels of two nodes (and no further in…
Dispersion on Trees
Paweł Gawrychowski, Nadav Krasnopolsky, Shay Mozes +1
In the -dispersion problem, we need to select nodes of a given graph so as to maximize the minimum distance between any two chosen nodes. This can be seen as a generalizatio…
A Faster Construction of Greedy Consensus Trees
Paweł Gawrychowski, Gad M. Landau, Wing-Kin Sung +1
A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in p…
Optimal Query Time for Encoding Range Majority
Pawel Gawrychowski, Patrick K. Nicholson
We revisit the range -majority problem, which asks us to preprocess an array for a fixed value of , such that for any query range we can return a…