10 citations · 15 across the 7 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.DC2016
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…
cs.DS2016
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…