Greg Bodwin | DeepAI

DeepAI AI Chat

Featured Co-authors

Stephen Kobourov
51 publications
Bernhard Haeupler
39 publications
Merav Parter
36 publications
Amir Abboud
27 publications
Michael Dinitz
23 publications
Keaton Hamm
21 publications
Nicole Wein
20 publications
Santosh Vempala
19 publications
Reyan Ahmed
18 publications
Aaron Bernstein
17 publications
Yasamin Nazari
15 publications

∙ 09/14/2023

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths

The restoration lemma is a classic result by Afek, Bremler-Barr, Kaplan,...

0 Greg Bodwin, et al. ∙

∙ 09/13/2023

Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free

We study a new and stronger notion of fault-tolerant graph structures wh...

0 Greg Bodwin, et al. ∙

∙ 08/26/2023

Spanning Adjacency Oracles in Sublinear Time

Suppose we are given an n-node, m-edge input graph G, and the goal is to...

0 Greg Bodwin, et al. ∙

∙ 08/24/2023

Are there graphs whose shortest path structure requires large edge weights?

The aspect ratio of a weighted graph G is the ratio of its maximum edge ...

0 Aaron Bernstein, et al. ∙

∙ 05/29/2023

An Alternate Proof of Near-Optimal Light Spanners

In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] es...

0 Greg Bodwin, et al. ∙

∙ 04/05/2023

Folklore Sampling is Optimal for Exact Hopsets: Confirming the √(n) Barrier

For a graph G, a D-diameter-reducing exact hopset is a small set of addi...

0 Greg Bodwin, et al. ∙

∙ 12/22/2022

Bridge Girth: A Unifying Notion in Network Design

A classic 1993 paper by Althőfer et al. proved a tight reduction from sp...

0 Greg Bodwin, et al. ∙

∙ 09/08/2022

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas

In competitive games, it is common to assign each player a real number r...

0 Greg Bodwin, et al. ∙

∙ 09/08/2022

Epic Fail: Emulators can tolerate polynomially many edge faults for free

A t-emulator of a graph G is a graph H that approximates its pairwise sh...

0 Greg Bodwin, et al. ∙

∙ 07/24/2022

New Additive Spanner Lower Bounds by an Unlayered Obstacle Product

For an input graph G, an additive spanner is a sparse subgraph H whose s...

0 Greg Bodwin, et al. ∙

∙ 09/16/2021

Vertex Fault-Tolerant Emulators

A k-spanner of a graph G is a sparse subgraph that preserves its shortes...

0 Greg Bodwin, et al. ∙

∙ 03/17/2021

On additive spanners in weighted graphs with local error

An additive +β spanner of a graph G is a subgraph which preserves distan...

0 Reyan Ahmed, et al. ∙

∙ 02/22/2021

Partially Optimal Edge Fault-Tolerant Spanners

Recent work has established that, for every positive integer k, every n-...

0 Greg Bodwin, et al. ∙

∙ 02/19/2021

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs

The restoration lemma by Afek, Bremler-Barr, Kaplan, Cohen, and Merritt ...

0 Greg Bodwin, et al. ∙

∙ 02/11/2021

Multi-level Weighted Additive Spanners

Given a graph G = (V,E), a subgraph H is an additive +β spanner if _H(u,...

0 Reyan Ahmed, et al. ∙

∙ 07/16/2020

Optimal Vertex Fault-Tolerant Spanners in Polynomial Time

Recent work has pinned down the existentially optimal size bounds for ve...

0 Greg Bodwin, et al. ∙

∙ 02/15/2020

Weighted Additive Spanners

An α-additive spanner of an undirected graph G=(V, E) is a subgraph H su...

0 Reyan Ahmed, et al. ∙

∙ 01/21/2020

Some General Structure for Extremal Sparsification Problems

This paper is about a branch of theoretical computer science that studie...

0 Greg Bodwin, et al. ∙

∙ 11/26/2019

Matrix Decompositions and Sparse Graph Regularity

We introduce and study a matrix decomposition that is a common generaliz...

0 Greg Bodwin, et al. ∙

∙ 11/15/2019

Strategy-Stealing is Non-Constructive

In many combinatorial games, one can prove that the first player wins un...

0 Greg Bodwin, et al. ∙

∙ 09/07/2019

Graph Spanners: A Tutorial Review

This tutorial review provides a guiding reference to researchers who wan...

0 Reyan Ahmed, et al. ∙

∙ 12/14/2018

A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners

We give a short and easy upper bound on the worst-case size of fault tol...

0 Greg Bodwin, et al. ∙

∙ 04/25/2018

On the Structure of Unique Shortest Paths in Graphs

This paper develops a structural theory of unique shortest paths in real...

0 Greg Bodwin, et al. ∙

∙ 10/30/2017

Reachability Preservers: New Extremal Bounds and Approximation Algorithms

In this paper we prove new results about the extremal structure of paths...

0 Amir Abboud, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world