Richard Spence

activity

20182023

most citedMulti-Level Steiner Trees

9 citations · 15 across the 6 of their papers we have counts for

collaborators

Showing 2021Show all

3 papers · 1 filter

cs.DS2021

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 $G = (V, E)$ with a source $s \in V$ and terminals $T \subseteq V ∖ {s}$ , where each terminal $v…

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…