206 citations · 412 across the 29 of their papers we have counts for
6 papers · 1 filter
Efficient Dynamic Approximate Distance Oracles for Vertex-Labeled Planar Graphs
Itay Laish, Shay Mozes
Let be a graph where each vertex is associated with a label. A Vertex-Labeled Approximate Distance Oracle is a data structure that, given a vertex and a label , returns…
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…
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(…