206 citations · 303 across the 29 of their papers we have counts for
6 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…
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…
Voronoi diagrams on planar graphs, and computing the diameter in deterministic time
Paweł Gawrychowski, Haim Kaplan, Shay Mozes +2
We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let be a planar graph with vertices and sites that lie on a…
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
Karl Bringmann, Paweł Gawrychowski, Shay Mozes +1
The edit distance between two rooted ordered trees with nodes labeled from an alphabet~ is the minimum cost of transforming one tree into the other by a sequence of elementa…
Near-Optimal Compression for the Planar Graph Metric
Amir Abboud, Pawel Gawrychowski, Shay Mozes +1
The Planar Graph Metric Compression Problem is to compactly encode the distances among nodes in a planar graph of size . Two naïve solutions are to store the graph using $O(…