4 citations · 4 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
An Alternate Proof of Near-Optimal Light Spanners
Greg Bodwin
In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] established that every -node graph has a -spanner of lightness $O_{\varepsilon}(…
Folklore Sampling is Optimal for Exact Hopsets: Confirming the Barrier
Greg Bodwin, Gary Hoppenworth
For a graph , a -diameter-reducing exact hopset is a small set of additional edges that, when added to , maintains its graph metric but guarantees that all node pairs…