5 papers · 1 filter
Multi-level Weighted Additive Spanners
Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh +3
Given a graph , a subgraph is an \emph{additive spanner} if $\dist_H(u,v) \le \dist_G(u,v) + β$ for all . A \emph{pairwise spanner} is a spanner for…
On additive spanners in weighted graphs with local error
Reyan Ahmed, Greg Bodwin, Keaton Hamm +2
An \emph{additive spanner} of a graph is a subgraph which preserves distances up to an additive error. Additive spanners are well-studied in unweighted graphs but hav…
Graph Spanners: A Tutorial Review
Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh +4
This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literatur…
Multi-Level Graph Sketches via Single-Level Solvers
Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli +3
Given an undirected weighted graph , a constrained sketch over a terminal set is a subgraph that connects the terminal vertices while satisfying a given s…
Approximation algorithms and an integer program for multi-level graph spanners
Reyan Ahmed, Keaton Hamm, Mohammad Javad Latifi Jebelli +3
Given a weighted graph and , a subgraph is a \emph{--spanner} of if the lengths of shortest paths in are preserved in up to a multiplicative fa…