Approximation Algorithms for Directed Weighted Spanners

Elena Grigorescu, Nithish Kumar, Young-San Lin

In the pairwise weighted spanner problem, the input consists of an $n$-vertex-directed graph, where each edge is assigned a cost and a length. Given $k$ vertex pairs and a distance…