|
+
|
An Alternate Proof of Near-Optimal Light Spanners
|
2025
|
Greg Bodwin
|
|
+
PDF
Chat
|
Improved Online Reachability Preservers
|
2025
|
Greg Bodwin
Tuong Le
|
|
+
PDF
Chat
|
A Lower Bound for Light Spanners in General Graphs
|
2025
|
Greg Bodwin
Jeremy Flics
|
|
+
PDF
Chat
|
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
|
2025
|
Greg Bodwin
Lily Wang
|
|
+
PDF
Chat
|
Improved Online Reachability Preservers
|
2024
|
Greg Bodwin
Tuong Le
|
|
+
PDF
Chat
|
A Lower Bound for Light Spanners in General Graphs
|
2024
|
Greg Bodwin
Jeremy Flics
|
|
+
PDF
Chat
|
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
|
2024
|
Greg Bodwin
Gary Hoppenworth
Virginia Vassilevska Williams
Nicole Wein
Zixuan Xu
|
|
+
PDF
Chat
|
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
|
2024
|
Amir Abboud
Greg Bodwin
|
|
+
PDF
Chat
|
The Discrepancy of Shortest Paths
|
2024
|
Greg Bodwin
Chengyuan Deng
Jie Gao
Gary Hoppenworth
Jalaj Upadhyay
Chen Wang
|
|
+
PDF
Chat
|
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
|
2024
|
Greg Bodwin
Bernhard Haeupler
Merav Parter
|
|
+
PDF
Chat
|
An Alternate Proof of Near-Optimal Light Spanners
|
2024
|
Greg Bodwin
|
|
+
PDF
Chat
|
Bridge Girth: A Unifying Notion in Network Design
|
2023
|
Greg Bodwin
Gary Hoppenworth
Ohad Trabelsi
|
|
+
|
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
|
2023
|
Greg Bodwin
Merav Parter
|
|
+
|
Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
|
2023
|
Greg Bodwin
Gary Hoppenworth
|
|
+
|
An Alternate Proof of Near-Optimal Light Spanners
|
2023
|
Greg Bodwin
|
|
+
|
Are there graphs whose shortest path structure requires large edge weights?
|
2023
|
Aaron Bernstein
Greg Bodwin
Nicole Wein
|
|
+
|
Spanning Adjacency Oracles in Sublinear Time
|
2023
|
Greg Bodwin
Henry L. Fleischmann
|
|
+
|
Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free
|
2023
|
Greg Bodwin
Bernhard Haeupler
Merav Parter
|
|
+
|
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
|
2023
|
Greg Bodwin
Lily Wang
|
|
+
PDF
Chat
|
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
|
2022
|
Greg Bodwin
Gary Hoppenworth
|
|
+
PDF
Chat
|
Partially Optimal Edge Fault-Tolerant Spanners
|
2022
|
Greg Bodwin
Michael Dinitz
Caleb Robelle
|
|
+
|
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
|
2022
|
Greg Bodwin
Gary Hoppenworth
|
|
+
|
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
|
2022
|
Greg Bodwin
Forest Zhang
|
|
+
|
Epic Fail: Emulators can tolerate polynomially many edge faults for free
|
2022
|
Greg Bodwin
Michael Dinitz
Yasamin Nazari
|
|
+
|
Bridge Girth: A Unifying Notion in Network Design
|
2022
|
Greg Bodwin
Gary Hoppenworth
Ohad Trabelsi
|
|
+
PDF
Chat
|
A unified view of graph regularity via matrix decompositions
|
2021
|
Greg Bodwin
Santosh Vempala
|
|
+
PDF
Chat
|
Better Distance Preservers and Additive Spanners
|
2021
|
Greg Bodwin
Virginia Vassilevska Williams
|
|
+
PDF
Chat
|
A note on distance-preserving graph sparsification
|
2021
|
Greg Bodwin
|
|
+
PDF
Chat
|
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
|
2021
|
Greg Bodwin
Merav Parter
|
|
+
|
Weighted Sparse and Lightweight Spanners with Local Additive Error.
|
2021
|
Reyan Ahmed
Greg Bodwin
Keaton Hamm
Stephen Kobourov
Richard Spence
|
|
+
|
On additive spanners in weighted graphs with local error
|
2021
|
Reyan Ahmed
Greg Bodwin
Keaton Hamm
Stephen Kobourov
Richard Spence
|
|
+
PDF
Chat
|
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
|
2021
|
Greg Bodwin
Michael Dinitz
Caleb Robelle
|
|
+
|
Multi-level Weighted Additive Spanners
|
2021
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Keaton Hamm
Stephen Kobourov
Richard Spence
|
|
+
PDF
Chat
|
New Results on Linear Size Distance Preservers
|
2021
|
Greg Bodwin
|
|
+
PDF
Chat
|
On Additive Spanners in Weighted Graphs with Local Error
|
2021
|
Reyan Ahmed
Greg Bodwin
Keaton Hamm
Stephen Kobourov
Richard Spence
|
|
+
|
Vertex Fault-Tolerant Emulators
|
2021
|
Greg Bodwin
Michael Dinitz
Yasamin Nazari
|
|
+
|
On additive spanners in weighted graphs with local error
|
2021
|
Reyan Ahmed
Greg Bodwin
Keaton Hamm
Stephen Kobourov
RĂchard K. Spence
|
|
+
|
Partially Optimal Edge Fault-Tolerant Spanners
|
2021
|
Greg Bodwin
Michael Dinitz
Caleb Robelle
|
|
+
|
Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs
|
2021
|
Greg Bodwin
Merav Parter
|
|
+
PDF
Chat
|
Graph spanners: A tutorial review
|
2020
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Keaton Hamm
Mohammad Javad Latifi Jebelli
Stephen Kobourov
Richard Spence
|
|
+
|
Weighted Additive Spanners
|
2020
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Stephen Kobourov
Richard Spence
|
|
+
|
Some General Structure for Extremal Sparsification Problems.
|
2020
|
Greg Bodwin
|
|
+
|
A Note on Distance-Preserving Graph Sparsification
|
2020
|
Greg Bodwin
|
|
+
PDF
Chat
|
Weighted Additive Spanners
|
2020
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Stephen Kobourov
Richard Spence
|
|
+
|
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
|
2020
|
Greg Bodwin
Michael Dinitz
Caleb Robelle
|
|
+
|
Weighted Additive Spanners
|
2020
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Stephen Kobourov
RĂchard K. Spence
|
|
+
|
A Note on Distance-Preserving Graph Sparsification
|
2020
|
Greg Bodwin
|
|
+
|
Matrix Decompositions and Sparse Graph Regularity.
|
2019
|
Greg Bodwin
Santosh Vempala
|
|
+
|
A Unified View of Graph Regularity via Matrix Decompositions
|
2019
|
Greg Bodwin
Santosh Vempala
|
|
+
|
Strategy-Stealing is Non-Constructive
|
2019
|
Greg Bodwin
Ofer Grossman
|
|
+
|
Graph Spanners: A Tutorial Review
|
2019
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Keaton Hamm
Mohammad Javad Latifi Jebelli
Stephen Kobourov
Richard Spence
|
|
+
PDF
Chat
|
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
|
2019
|
Greg Bodwin
Shyamal Patel
|
|
+
|
On the structure of unique shortest paths in graphs
|
2019
|
Greg Bodwin
|
|
+
PDF
Chat
|
On the Structure of Unique Shortest Paths in Graphs
|
2019
|
Greg Bodwin
|
|
+
|
Strategy-Stealing Is Non-Constructive.
|
2019
|
Greg Bodwin
Ofer Grossman
|
|
+
|
A Unified View of Graph Regularity via Matrix Decompositions
|
2019
|
Greg Bodwin
Santosh Vempala
|
|
+
|
Strategy-Stealing is Non-Constructive
|
2019
|
Greg Bodwin
Ofer Grossman
|
|
+
|
Graph Spanners: A Tutorial Review
|
2019
|
Reyan Ahmed
Greg Bodwin
Faryad Darabi Sahneh
Keaton Hamm
Mohammad Javad Latifi Jebelli
Stephen Kobourov
RĂchard K. Spence
|
|
+
|
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
|
2018
|
Greg Bodwin
Shyamal Patel
|
|
+
PDF
Chat
|
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
|
2018
|
Amir Abboud
Greg Bodwin
Seth Pettie
|
|
+
PDF
Chat
|
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
|
2018
|
Amir Abboud
Greg Bodwin
|
|
+
PDF
Chat
|
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
|
2018
|
Greg Bodwin
Michael Dinitz
Merav Parter
Virginia Vassilevska Williams
|
|
+
|
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
|
2018
|
Greg Bodwin
Shyamal Patel
|
|
+
|
On the Structure of Unique Shortest Paths in Graphs
|
2018
|
Greg Bodwin
|
|
+
PDF
Chat
|
The 4/3 Additive Spanner Exponent Is Tight
|
2017
|
Amir Abboud
Greg Bodwin
|
|
+
|
Preserving Distances in Very Faulty Graphs
|
2017
|
Greg Bodwin
Fabrizio Grandoni
Merav Parter
Virginia Vassilevska Williams
|
|
+
|
Linear Size Distance Preservers
|
2017
|
Greg Bodwin
|
|
+
|
Testing Core Membership in Public Goods Economies
|
2017
|
Greg Bodwin
|
|
+
|
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
|
2017
|
Amir Abboud
Greg Bodwin
Seth Pettie
|
|
+
|
Preserving Distances in Very Faulty Graphs
|
2017
|
Greg Bodwin
Fabrizio Grandoni
Merav Parter
Virginia Vassilevska Williams
|
|
+
|
Testing Core Membership in Public Goods Economies.
|
2017
|
Greg Bodwin
|
|
+
|
Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
|
2017
|
Greg Bodwin
Michael Dinitz
Merav Parter
Virginia Vassilevska Williams
|
|
+
|
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
|
2017
|
Amir Abboud
Greg Bodwin
|
|
+
|
The 4/3 additive spanner exponent is tight
|
2016
|
Amir Abboud
Greg Bodwin
|
|
+
|
New Results on Linear Size Distance Preservers
|
2016
|
Greg Bodwin
|
|
+
|
Fully Dynamic Spanners with Worst-Case Update Time
|
2016
|
Greg Bodwin
Sebastian Krinninger
|
|
+
|
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
|
2016
|
Amir Abboud
Greg Bodwin
Seth Pettie
|
|
+
|
New Results on Linear Size Distance Preservers
|
2016
|
Greg Bodwin
|
|
+
PDF
Chat
|
Better Distance Preservers and Additive Spanners
|
2015
|
Greg Bodwin
Virginia Vassilevska Williams
|
|
+
|
The 4/3 Additive Spanner Exponent is Tight
|
2015
|
Amir Abboud
Greg Bodwin
|
|
+
|
Very Sparse Additive Spanners and Emulators
|
2015
|
Greg Bodwin
Virginia Vassilevska Williams
|
|
+
|
Very Sparse Additive Spanners and Emulators
|
2015
|
Greg Bodwin
Virginia Vassilevska Williams
|
|
+
|
The 4/3 Additive Spanner Exponent is Tight
|
2015
|
Amir Abboud
Greg Bodwin
|
|
+
|
Better Distance Preservers and Additive Spanners
|
2015
|
Greg Bodwin
Virginia Vassilevska Williams
|