2 citations · 3 across the 10 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.DS2015★ 1 cited
The 4/3 Additive Spanner Exponent is Tight
Amir Abboud, Greg Bodwin
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a…
cs.DS2015★ 2 cited
Very Sparse Additive Spanners and Emulators
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…
cs.DS2015
Better Distance Preservers and Additive Spanners
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…