4 citations · 4 across the 1 of their papers we have counts for
5 papers · 1 filter
Partially Optimal Edge Fault-Tolerant Spanners
Greg Bodwin, Michael Dinitz, Caleb Robelle
Recent work has established that, for every positive integer , every -node graph has a -spanner on edges that is resilient to edge or ver…
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Greg Bodwin, Michael Dinitz, Caleb Robelle
Recent work has pinned down the existentially optimal size bounds for vertex fault-tolerant spanners: for any positive integer , every -node graph has a -spanner on $…
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…
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…
Preserving Distances in Very Faulty Graphs
Greg Bodwin, Fabrizio Grandoni, Merav Parter +1
Preservers and additive spanners are sparse (hence cheap to store) subgraphs that preserve the distances between given pairs of nodes exactly or with some small additive error, res…