23 citations · 27 across the 7 of their papers we have counts for
10 papers
All-Hops Shortest Paths
Virginia Vassilevska Williams, Zoe Xi, Yinzhan Xu +1
Let be a weighted directed graph without negative cycles. For two vertices , we let be the minimum, according to the weight function , of…
Faster Cycle Detection in the Congested Clique
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
We provide a fast distributed algorithm for detecting -cycles in the \textsf{Congested Clique} model, whose running time decreases as the number of -cycles in the graph incre…
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu +1
Single Source Shortest Paths () is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain…
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation
Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams +1
Roundtrip spanners are the analog of spanners in directed graphs, where the roundtrip metric is used as a notion of distance. Recent works have shown existential results of roundtr…
Listing 6-Cycles
Ce Jin, Virginia Vassilevska Williams, Renfei Zhou
Listing copies of small subgraphs (such as triangles, -cycles, small cliques) in the input graph is an important and well-studied problem in algorithmic graph theory. In this pa…
Simpler and Higher Lower Bounds for Shortcut Sets
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu
We provide a variety of lower bounds for the well-known shortcut set problem: how much can one decrease the diameter of a directed graph on vertices and edges by adding $O(…