11 citations · 16 across the 14 of their papers we have counts for
Showing 2016 · cs.DSShow all
3 papers · 2 filters
cs.DS2016
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Amir Abboud, Greg Bodwin, Seth Pettie
Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say …
cs.DS2016★ 11 cited
Fully Dynamic Spanners with Worst-Case Update Time
Greg Bodwin, Sebastian Krinninger
An -spanner of a graph is a subgraph such that preserves all distances of within a factor of . In this paper, we give fully dynamic algorithms for ma…
cs.DS2016
New Results on Linear Size Distance Preservers
Greg Bodwin
Given node pairs in an -node graph, a distance preserver is a sparse subgraph that agrees with the original graph on all of the given pairwise distances. We prove the follow…