9 citations · 15 across the 6 of their papers we have counts for
11 papers
Multi-Priority Graph Sparsification
Reyan Ahmed, Keaton Hamm, Stephen Kobourov +3
A \emph{sparsification} of a given graph is a sparser graph (typically a subgraph) which aims to approximate or preserve some property of . Examples of sparsifications inclu…
Approximation algorithms for priority Steiner tree problems
Faryad Darabi Sahneh, Stephen Kobourov, Richard Spence
In the Priority Steiner Tree (PST) problem, we are given an undirected graph with a source and terminals , where each terminal $v…
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…
Weighted Additive Spanners
Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh +2
A \emph{spanner} of a graph is a subgraph that approximately preserves shortest path distances in . Spanners are commonly applied to compress computation on metric space…
Kruskal-based approximation algorithm for the multi-level Steiner tree problem
Reyan Ahmed, Faryad Darabi Sahneh, Keaton Hamm +2
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals require varying priority, level, or quality of service. In…
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…
Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem
Faryad Darabi Sahneh, Alon Efrat, Stephen Kobourov +2
Given a graph and a subset of terminals, a \emph{Steiner tree} of is a tree that spans . In the vertex-weighted Steiner tree (VST) problem, each…
Multi-Level Steiner Trees
Reyan Ahmed, Patrizio Angelini, Faryad Darabi Sahneh +8
In the classical Steiner tree problem, given an undirected, connected graph with non-negative edge costs and a set of \emph{terminals} , the objective is to…