49 citations · 193 across the 39 of their papers we have counts for
4 papers · 2 filters
A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh
We consider the minimum-weight feedback vertex set problem in tournaments: given a tournament with non-negative vertex weights, remove a minimum-weight set of vertices that interse…
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter
Amir Abboud, Virginia Vassilevska Williams, Joshua Wang
The radius and diameter are fundamental graph parameters. They are defined as the minimum and maximum of the eccentricities in a graph, respectively, where the eccentricity of a ve…
Very Sparse Additive Spanners and Emulators
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…
Better Distance Preservers and Additive Spanners
Greg Bodwin, Virginia Vassilevska Williams
We study two popular ways to sketch the shortest path distances of an input graph. The first is distance preservers, which are sparse subgraphs that agree with the distances of the…