6 citations · 12 across the 3 of their papers we have counts for
3 papers · 1 filter
Approximating the diameter of a graph
Liam Roditty, Virginia Vassilevska Williams
In this paper we consider the fundamental problem of approximating the diameter of directed or undirected graphs. In a seminal paper, Aingworth, Chekuri, Indyk and Motwani [SIA…
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
Liam Roditty, Virginia Vassilevska Williams
We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirec…
Finding heaviest H-subgraphs in real weighted graphs, with applications
Virginia Vassilevska, Ryan Williams, Raphael Yuster
For a graph G with real weights assigned to the vertices (edges), the MAX H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if one exists. The all-pairs M…