10 citations · 10 across the 2 of their papers we have counts for
5 papers
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(…
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel, Seri Khoury
We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Speci…
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
Amir Abboud, Søren Dahlgaard
The dynamic shortest paths problem on planar graphs asks us to preprocess a planar graph such that we may support insertions and deletions of edges in as well as distance q…
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
Amir Abboud, Virginia Vassilevska Williams, Joshua Wang
The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a ve…
Exact Weight Subgraphs and the k-Sum Conjecture
Amir Abboud, Kevin Lewi
We consider the Exact-Weight-H problem of finding a (not necessarily induced) subgraph H of weight 0 in an edge-weighted graph G. We show that for every H, the complexity of this p…