2 citations · 3 across the 10 of their papers we have counts for
4 papers · 1 filter
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 -expa…
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…
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 $…
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…