3 papers
cs.DS2023
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
Greg Bodwin, Bernhard Haeupler, Merav Parter
We study a new and stronger notion of fault-tolerant graph structures whose size bounds depend on the degree of the failing edge set, rather than the total number of faults. For a…
cs.DS2022
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
Greg Bodwin, Gary Hoppenworth
For an input graph , an additive spanner is a sparse subgraph whose shortest paths match those of up to small additive error. We prove two new lower bounds in the area o…
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 …