Publications (44)
Vertex Fault-Tolerant Emulators
Greg Bodwin, Michael Dinitz, Yasamin Nazari
A -spanner of a graph is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of , and a -emulator is similar but not req…
Bridge Girth: A Unifying Notion in Network Design
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
A classic 1993 paper by AlthÅfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function of high-girth graphs. This paper init…
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
Greg Bodwin, Shyamal Patel
We give a short and easy upper bound on the worst-case size of fault tolerant spanners, which improves on all prior work and is fully optimal at least in the setting of vertex faul…
Strategy-Stealing is Non-Constructive
Greg Bodwin, Ofer Grossman
In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the…
Testing Core Membership in Public Goods Economies
Greg Bodwin
This paper develops a recent line of economic theory seeking to understand public goods economies using methods of topological analysis. Our first main result is a very clean chara…
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
Greg Bodwin, Michael Dinitz, Merav Parter +1
A -spanner of a graph is a sparse subgraph whose shortest path distances match those of up to a multiplicative error . In this paper we study spanners that are re…