4 papers
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…
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…
A Unified View of Graph Regularity via Matrix Decompositions
Greg Bodwin, Santosh Vempala
We prove algorithmic weak and \Szemeredi{} regularity lemmas for several classes of sparse graphs in the literature, for which only weak regularity lemmas were previously known. Th…
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}(…