7 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…
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…
Simple Length-Constrained Expander Decompositions
Greg Bodwin, Bernhard Haeupler, D Ellis Hershkowitz +1
Length-constrained expander decompositions are a new graph decomposition that has led to several recent breakthroughs in fast graph algorithms. Roughly, an -length -exp…
Notes on the Linear Algebraic View of Regularity Lemmas
Greg Bodwin, Tuong Le
When regularity lemmas were first developed in the 1970s, they were described as results that promise a partition of any graph into a ``small'' number of parts, such that the graph…
Light Edge Fault Tolerant Graph Spanners
Greg Bodwin, Michael Dinitz, Ama Koranteng +1
There has recently been significant interest in fault tolerant spanners, which are spanners that still maintain their stretch guarantees after some nodes or edges fail. This work h…
Multiplicative Spanners in Minor-Free Graphs
Greg Bodwin, Gary Hoppenworth, Zihan Tan
In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $…