10 citations · 10 across the 7 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022
Bridge Girth: A Unifying Notion in Network Design
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
A classic 1993 paper by Althőfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function of high-girth graphs. This paper initia…
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…