11 citations · 16 across the 14 of their papers we have counts for
29 papers
Unconditional Lower Bounds for Degree Fault Tolerant Spanners
Greg Bodwin, Aleksey Lopez
We study multiplicative graph spanners in the -degree fault tolerant (-DFT) model, in which the spanner must approximately preserve distances even after any subset of edges o…
Improved Upper Bounds for the Directed Flow-Cut Gap
Greg Bodwin, Luba Samborska
We prove that the flow-cut gap for -node directed graphs is at most . This is the first improvement since a previous upper bound of by…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
A Lower Bound for Light Spanners in General Graphs
Greg Bodwin, Jeremy Flics
A recent upper bound by Le and Solomon [STOC '23] has established that every -node graph has a -spanner with lightness . This…
Spanning Adjacency Oracles in Sublinear Time
Greg Bodwin, Henry Fleischmann
Suppose we are given an -node, -edge input graph , and the goal is to compute a spanning subgraph on edges. This can be achieved in linear time via b…
Are there graphs whose shortest path structure requires large edge weights?
Aaron Bernstein, Greg Bodwin, Nicole Wein
The aspect ratio of a (positively) weighted graph is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in gr…