Richard Spence

activity

20182021

collaborators

Showing cs.DSShow 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.DS2020

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 $T$ require varying priority, level, or quality of service. In…

cs.DS2018

Approximation algorithms for the vertex-weighted grade-of-service Steiner tree problem

Faryad Darabi Sahneh, Alon Efrat, Stephen Kobourov +2

Given a graph $G = (V, E)$ and a subset $T \subseteq V$ of terminals, a \emph{Steiner tree} of $G$ is a tree that spans $T$ . In the vertex-weighted Steiner tree (VST) problem, each…