Gregory Bodwin

activity

20172026

most citedPreserving Distances in Very Faulty Graphs

4 citations · 4 across the 4 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DM2021

Multi-level Weighted Additive Spanners

Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh +3

Given a graph $G = (V, E)$ , a subgraph $H$ is an \emph{additive $+ β$ spanner} if $\dist_H(u,v) \le \dist_G(u,v) + β$ for all $u, v \in V$ . A \emph{pairwise spanner} is a spanner for…

cs.DM2021

On additive spanners in weighted graphs with local error

Reyan Ahmed, Greg Bodwin, Keaton Hamm +2

An \emph{additive $+ β$ spanner} of a graph $G$ is a subgraph which preserves distances up to an additive $+ β$ error. Additive spanners are well-studied in unweighted graphs but hav…

cs.DS2021

Partially Optimal Edge Fault-Tolerant Spanners

Greg Bodwin, Michael Dinitz, Caleb Robelle

Recent work has established that, for every positive integer $k$ , every $n$ -node graph has a $(2 k - 1)$ -spanner on $O (f^{1 - 1/ k} n^{1 + 1/ k})$ edges that is resilient to $f$ edge or ver…